[백준/파이썬] 2665번

📍백준 2665번 문제

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

코드

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

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
n = int(input())
visited = [[-1 for _ in range(n)] for _ in range(n)]

room = []
for _ in range(n):
    room.append(list(input().rstrip('\n')))

que = deque()
x, y = 0, 0
que.append((x, y))
visited[0][0] = 0
while que:
    x, y = que.popleft()
    if x == n-1 and y == n-1:
        print(visited[n-1][n-1])
        break
    for i in range(4):
        nx = x+dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == -1:
            if room[nx][ny] == '1':
                visited[nx][ny] = visited[x][y]
                que.appendleft((nx, ny))
            elif room[nx][ny] == '0':
                visited[nx][ny] = visited[x][y]+1
                que.append((nx, ny))

풀이

• BFS와 deque를 이용해서 풀었다.
• 1인 경우가 우선순위가 더 높으므로 appendleft를 이용하여 que의 맨 앞에 가져다 주었고, visited[nx][ny]값은 이전에 방문한 값으로 넣어주었다.
• 0인 경우는 append를 이용하여 que의 뒤에 넣었고, visited[nx][ny]값은 검은방을 흰방으로 바꿨으므로 이전 값에 1을 더해서 넣어준다.