[BOJ] 2665. 미로만들기(Python) / BFS

www.acmicpc.net/problem/2665

2665번: 미로만들기

고민을 꽤 했던 BFS 최단거리 미로 만들기 문제였다.

벽이 있을 때, 뚫을 수 있되 가장 적게 벽을 뚫고 목적지까지 도달하도록 하는 것이다.

• visited를 각 위치별로 최댓값 float('inf')으로 초기화한다.
• maze[nr][nc]가 vistied의 해당 위치를 최솟값으로 갱신할 수 있을 때만 갱신하고 큐에 값을 담는다.
• 이 때, 빈 공간이라면 벽을 뚫지 않고도 그냥 이동할 수 있으므로 해당 빈 공간의 위치를 우선순위를 높게 쳐서 큐의 헤드 부분에 넣어준다(appendleft((nr, nc)). 
• 그렇지 않다면 빈 공간이든, 벽이든 기존의 값을 갱신할 수 있을 때만 갱신하고 위치를 큐에 담는다.
• 목적지에 다다르면 그 때의 cnt값(벽 뚫은 횟수)를 리턴한다.

 

파이썬 코드는 다음과 같다.

---

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

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs():
    visited = [[float('inf')] * N for _ in range(N)]    # 최댓값으로 초기화
    visited[0][0] = 0
    Q = deque([(0, 0, 0)])
    while Q:
        r, c, cnt = Q.popleft()
        if (r, c) == (N-1, N-1):        # 목적지 흰 방에 도달하면 리턴
            print(cnt)
            return
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < N and 0 <= nc < N):   # 격자 밖으로 나가면
                continue

            # 이동할 곳이 흰 방일 때 최솟값으로 갱신할 수 있는 곳일 때만 값 갱신
            if maze[nr][nc] == '1' and visited[nr][nc] > visited[r][c]+1:
                visited[nr][nc] = cnt
                Q.appendleft((nr, nc, cnt))

            # 이동할 곳이 검은 방일 때
            if maze[nr][nc] == '0':
                # 이미 방문했다면 최솟값으로 갱신할 수 있는 곳일 때만 값 갱신
                if visited[nr][nc] != float('inf') and visited[r][c] + 1 < visited[nr][nc]:
                    visited[nr][nc] = cnt + 1
                    Q.append((nr, nc, cnt + 1))
                # 아직 방문하지 않았다면 첫 방문이므로 검은 방을 흰 방으로 갱신
               if visited[nr][nc] == float('inf'):
                    visited[nr][nc] = cnt + 1
                    Q.append((nr, nc, cnt + 1))

# main
N = int(input())
maze = [list(input().strip()) for _ in range(N)]
bfs()

---

• 시간 : 162ms / 메모리 : 125944kb
• 고찰 : appendleft()를 미처 생각하지 못해 `메모리 초과`가 꽤 많이 났다ㅠㅠ 다른 풀이를 보고서야 우선순위를 높이 쳐서 큐의 헤드로 넣어줘야 한단 것을 깨달았다. 새로운 것 하나를 배웠다!

---

참, 그리고 참고한 코드 중에 최댓값이 아닌 0으로 초기화하여 첫 조건에 맞을 때만 위치 값을 갱신시켜 푼 코드도 있어서 참고로 올린다. 이는 시간 : 152ms / 메모리 : 125492kb로 내 코드보다 효율적인 기록을 낸다.

솔루션 원리는 같다. 빈 공간인 것을 큐의 앞에 넣어서 미리 꺼내서 갈 수 있는 곳을 갱신한다.

---

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

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs():
    visited = [[-1] * N for _ in range(N)]
    visited[0][0] = 0
    Q = deque([(0, 0)])
    while Q:
        r, c = Q.popleft()
        if (r, c) == (N-1, N-1):
            print(visited[N-1][N-1])
            return
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < N and 0 <= nc < N):
                continue
            if visited[nr][nc] == -1:
                if maze[nr][nc] == '1':
                    visited[nr][nc] = visited[r][c]
                    Q.appendleft((nr, nc))
                elif maze[nr][nc] == '0':
                    visited[nr][nc] = visited[r][c] + 1
                    Q.append((nr, nc))

N = int(input())
maze = [list(input().strip()) for _ in range(N)]
bfs()

---

내 코드보다 훨씬 깔끔하다 ㅋㅋㅋ appendleft()를 사용하는 문제가 종종 나올 수 있다는 것도 염두에 두고 적극 활용해야겠다!