백준 2665번

📖 문제

해결 과정

from collections import deque

n = int(input())
graph = [list(map(int, input())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
step = [[0] * n for _ in range(n)]
q = deque()

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

➡️ 검은 방과 흰 방을 나타낸 graph를 입력 받는다. 그리고 visited 배열을 통해 방문한 노드와 아직 방문하지 않은 노드를 구분짓고, step 배열을 이용해 각 셀에 도달하는 데 변경해야 할 횟수를 기록한다. 검은 방을 만나기 전까진 흰 방을 바꾸지 않아도 되므로 초기값은 0으로 초기화 해 줬다.

def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

def push(x, y, s):
    step[x][y] = s
    visited[x][y] = True
    if graph[x][y] == 1:
        q.appendleft((x, y))  # 흰 방은 큐의 앞에 추가
    else:
        q.append((x, y))  # 검은 방은 큐의 뒤에 추가

➡️ in_range() 함수는 graph를 탐색하는 동안 범위 밖으로 벗어나진 않았는지 체크해 준다. 그리고 push() 함수를 이용해 step 배열의 값을 업데이트 한다.
➡️ 문제에서 흰 방을 검은 방으로 바꾸는 횟수를 최소화 하라고 했으므로 흰 방을 먼저 탐색해 비용이 적게 드는 경로를 먼저 찾고, 검은 방은 나중에 바꿔야 할 경우에만 바꾸도록 한다.

def bfs():
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if in_range(nx, ny) and not visited[nx][ny]:
                if graph[nx][ny] == 1:
                    push(nx, ny, step[x][y])
                else:
                    push(nx, ny, step[x][y] + 1)

➡️ 이 과정에서 step 배열에 저장된 값은 흰 방으로 도착할 때는 그대로 유지되고, 검은 방으로 도착할 때는 이전 값에서 1씩 추가됨을 알 수 있다. 이를 통해 검은 방의 최소 변경 횟수를 구한다.

💡 문제 예시에 의해 도출된 step 배열

💡 전체 코드

from collections import deque

n = int(input())
graph = [list(map(int, input())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
step = [[0] * n for _ in range(n)]
q = deque()

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

def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

def push(x, y, s):
    step[x][y] = s
    visited[x][y] = True
    if graph[x][y] == 1:
        q.appendleft((x, y))  # 흰 방은 큐의 앞에 추가
    else:
        q.append((x, y))  # 검은 방은 큐의 뒤에 추가

def bfs():
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if in_range(nx, ny) and not visited[nx][ny]:
                if graph[nx][ny] == 1:
                    push(nx, ny, step[x][y])
                else:
                    push(nx, ny, step[x][y] + 1)

push(0, 0, 0)
bfs()

# 도착 지점의 최소 변경 횟수 출력
print(step[n-1][n-1])