[백준 11967] 불켜기 Python

📘 문제 정보

https://www.acmicpc.net/problem/11967

 

📝 문제 해석

• N × N 크기의 방이 있고, 각 방은 벽으로 막혀 있으며 상하좌우 인접한 방으로만 이동할 수 있다. (0, 0)에서 시작하여 이동 가능한 범위 내에서 불을 켤 수 있는 방을 최대한 켠 뒤, 전체 불이 켜진 방의 개수를 구하는 것이 목표다.
• 특정 방에는 스위치가 있어서 다른 방의 불을 켤 수 있다. 불이 꺼져 있는 방은 방문할 수 없고, 불이 켜진 방이라도 인접한 방문한 방이 있어야 실제로 방문이 가능하다.

 

💡 풀이 아이디어

이 문제는 다음 두 가지 조건을 동시에 고려해야 한다:

1. 불이 켜져 있어야 방문할 수 있다
2. 인접한 방문한 방이 있어야 실제로 이동(진입)할 수 있다

이를 해결하기 위해 다음 두 개의 상태를 구분하여 처리한다:

• light[][]: 각 방의 불이 켜졌는지 여부
• visited[][]: 실제로 방문한 적이 있는지 여부

 

✅ 핵심 전략

• light[][]: 불 켜진 상태, visited[][]: 방문 여부
• BFS를 사용하면서 다음을 반복한다:
  1. 현재 위치에 있는 스위치를 작동해 불을 켠다.
  2. 새롭게 불이 켜진 방이 기존에 방문한 방과 인접하다면, 즉시 방문 가능 → 큐에 추가
  3. 현재 위치에서 인접한 불 켜진 방들 중 아직 방문하지 않은 방을 찾아 큐에 추가

# pypy3

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
arr = [[[] for _ in range(n)] for _ in range(n)]
for _ in range(m):
    x, y, a, b = map(int, input().split())
    arr[x-1][y-1].append([a-1, b-1])

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

queue = deque()
queue.append([0, 0])
light = [[False] * n for _ in range(n)] # 불 켜진 상태
visited = [[False] * n for _ in range(n)] # 실제 방문한 방
light[0][0] = True
visited[0][0] = True
while queue:
    x, y = queue.popleft()
    # 스위치 작동하여 불 켜기
    for a, b in arr[x][y]:
        if not light[a][b]:
            light[a][b] = True
            # 불 켠 방이 인접 방문한 방과 붙어 있으면 방문 처리
            for k in range(4):
                na, nb = a + dx[k], b + dy[k]
                if 0 <= na < n and 0 <= nb < n and visited[na][nb]:
                    queue.append([a, b])
                    visited[a][b] = True
                    break

    # 인접한 불 켜진 방 탐색
    for k in range(4):
        nx, ny = x + dx[k], y + dy[k]
        if 0 <= nx < n and 0 <= ny < n and light[nx][ny] and not visited[nx][ny]:
            queue.append([nx, ny])
            visited[nx][ny] = True

answer = 0
for l in light:
    answer += l.count(True)
print(answer)