(백준 알고리즘 문제풀이) 2665번 미로만들기

문제

 

문제 링크

 

문제 접근

• N x N의 바둑판
• 흰방(1): 통과가 가능하다
• 검은방(0): 통과가 불가능하다
• (1,1)에서 (8,8)을 가기 위해서 검은방을 흰방으로 최소한으로 바꿔서 통과하라
• 상하좌우에 visited를 이용하여 탐색을 하지 않은 곳은 인접 이전 visited값이나 visited +1값으로 변경
• 만약 흰방(1)일 경우에는 q.appendleft를 이용하여 우선 탐색(popleft를 사용하기 때문)하고 이전 visited값과 동일하게 해준다. 
• 하지만 검은 방(0)일 경우에는 q.append를 이용하여 후순위로 미룬다. 그리고 visited + 1을 해준다. (찾는 것이 검은방을 흰방으로 변경하는 개수를 최소화한 것을 출력하라고 했기 때문이다)

코드

import sys
from collections import deque


def BFS(board):
    q = deque()
    q.append((0, 0))
    visited = list([-1] * N for _ in range(N))
    # 처음 위치는 방문한 것으로 가정
    visited[0][0] = 0

    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        # print(q)
        x, y = q.popleft()
        # 도착지에 도착했을 경우 return
        if x == N-1 and y == N-1:
            return visited[x][y]
        for i in range(len(d)):
            dx = x + d[i][0]
            dy = y + d[i][1]
            if (0 <= dx < N) and (0 <= dy < N) and visited[dx][dy] == -1:
                # 흰방일 경우
                if board[dx][dy] == 1:
                    # 우선탐색
                    q.appendleft((dx, dy))
                    visited[dx][dy] = visited[x][y]
                # 검은방일 경우
                else:
                    q.append((dx, dy))
                    visited[dx][dy] = visited[x][y] + 1


N = int(sys.stdin.readline())
board = list()
for _ in range(N):
    board.append(list(map(int, sys.stdin.readline().strip())))

print(BFS(board))

느낀점

BFS는 정말 많은 코딩테스트 문제를 푸는데에 사용이 되는 것을 느끼게 되었다.

앞으로 더욱 BFS를 잘 사용하기 위해서 많은 공부를 집중적으로 해보아야겠다.