[백준] 2554 : 미로만들기

문제

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

BFS와 heap을 사용해서 계속 내가 동서남북으로 이동할 수 있는 좌표 중 최소 비용(벽을 뚫는 횟수)을 가지는 좌표로만 이동하게 하는 것이 핵심!
그때 이미 while heap: 안에서 계속 최소 비용을 가지는 좌표로만 이동해주고 있으므로, visited했던 곳을 또 방문할 필요가 없어진다. visited 방문 기록을 남겨주는 이유가 바로 그것! 방문했던 곳을 방문하지 않게 하려고!!

풀이

풀이 1.

import heapq
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


n = int(input())
maze = [list(map(int,list(input().strip()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
# print(maze)

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

heap = [(0,0,0)]
while heap:
    # heap을 쓰는 이유
    # 최소의 개수로 검은 방을 지나가야 하기 때문에 
    # 비용이 적은 흰색 방을 최대한 많이 거쳐가야 함!
    # 그래서 내가 갈 수 있는 곳 중 비용이 적은 방들을 먼저 탐색해주기 위해 (= 벽을 덜 뿌시기 위해)
    # heappop()을 이용해서 비용 적은 흰 방부터 탐색을 들어감!
    # 이후에 비용이 높은 방인 검은 방을 탐색해주는 것!
     
    (cnt, cx, cy) = heapq.heappop(heap)

    if cx == n-1 and cy == n-1:
        print(cnt)
        break  
    maze[cy][cx] = cnt
    for i in range(4):
        nx = cx + dx[i]
        ny = cy + dy[i]

        if 0 <= nx < n and 0 <= ny < n:
            # 흰색인 경우
            if maze[ny][nx] == 1 and not visited[ny][nx]: 
            # visited 쓰는 이유 : 최단 거리는 최단 거리가 갱신되면 남겨둬야 함 (더 더할 필요 없음)
                heapq.heappush(heap, (cnt, nx, ny))

            # 회색인 경우
            elif maze[ny][nx] == 0 and not visited[ny][nx]:
                heapq.heappush(heap, (cnt+1, nx, ny))

            visited[ny][nx] = True
            

풀이 2.

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

N = int(input())
bang = [[] for i in range(N+1)]

for i in range(1, N+1):
    bang[i] = [1] + list(map(int, input().strip())) # 이어져 있는 문자열을 int형으로 하나씩 넣기 (but 0번째 방은 임의의 수 1을 주기)

visited = [[False for _ in range(N+1)] for _ in range(N+1)]

# 좌표 이동
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

# 다익스트라
def dijkstra(x, y):
    q = []
    heapq.heappush(q, (0, x, y)) # 벽을 뿌실 때마다 발생하는 비용, x좌표, y좌표

    while q: # 큐가 비어있지 않으면
        # 거리, 방 위치 
        cost, r, c = heapq.heappop(q) # dist는 현재까지 0의 개수
        
        # 목적지에 도달했을 경우
        if r == N and c == N:
            return cost
        
        if visited[r][c]: # 이미 방문했었으면 더이상 따지지 않음
            continue
        
        visited[r][c] = True
        
        # 동서남북으로 이동하면서 0인 것의 개수 세기
        for i in range(4):
            dr, dc = r + dx[i], c + dy[i]
            if dr <= 0 or dr > N or dc <= 0 or dc > N:
                continue
            
            if bang[dr][dc] == 1:
                heapq.heappush(q, (cost, dr, dc)) # 기존에 꺼낸 것의 cost를 그대로 넣어줌 (벽을 뿌시지 않았기 때문)
            else:
                heapq.heappush(q, (cost+1, dr, dc)) # 검은방이었으면 cost에 1을 더해서 넣어줌
                
answer = dijkstra(1,1)

print(answer)

다익스트라 풀이

# 민성님 코드
import heapq
import sys
input = sys.stdin.readline

N = int(input())
matrix = [list(map(int, input().rstrip())) for _ in range(N)]
distance = [[int(10e9)]*N for _ in range(N)]

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

min_path = 2500

def bfs():              # 사실 다익스트라
    heap = []
    heapq.heappush(heap, (0,0,0))
    while heap:
        cost, r, c = heapq.heappop(heap)

        if distance[r][c] <= cost:
            continue
        else:
            distance[r][c] = cost

        for i in range(4):
            nx = r + dx[i]
            ny = c + dy[i]

            if nx >=0 and nx < N and ny >=0 and ny < N:
                if not matrix[nx][ny]:
                    heapq.heappush(heap, (cost+1, nx, ny))
                else:
                    heapq.heappush(heap, (cost, nx, ny))

bfs()

print(distance[N-1][N-1])