[백준 1261번] 알고스팟

고민했던 것들

1. 갑자기 이차원 배열을 입력받으라고 하니 당황스러웠다. 그래서 리스트 하나를 만들고, 한 줄씩 리스트 형태로 만들어서 추가하려는데 자꾸 '\n' 문자가 끼어든다. 이거 왜이러지?

2. (1,1)에서 (N,M) 으로 갈 수 있는 경우에 최단 경로 구하는 것은 쉬운데, 만약 벽으로 막혀 있다면 어떻게 뚫어서 갈 것인가?

3. 이 문제가 다익스트라 알고리즘 문제라고? ㅋㅋ...

정말 고민들을 날 것 그대로 나열하면 이런 고민들을 가졌다.

고민 해결 방법

1번 고민

1번 고민은 솔직히 부끄러운 것이긴 한데, input = sys.stdin.readline 문장 자체를 이번에 처음 사용해 본 것이라 발생된 문제였다. 파이썬에서 시간 초과를 극복하기 위해 이 방법을 사용하는 것인데, 이 것을 사용하게 되면 개행 문자 '\n'가 마지막에 반드시 삽입된다는 문제가 있었다. 고로 이 뒤에 .rstrip()을 붙여주면 해결되는 문제였다.

2, 3번 고민

그림을 그려 직관적으로 생각해보기로 했다. 그림은 입력 예시 3을 그려서 생각해보았다.

그림을 그리고 생각해보니, 2번 고민 방식으로는 접근해서는 안될 문제 같았다. 이 문제는 최단 경로 문제가 아니라, 벽을 최소한으로 뚫는 방법을 생각해내는 문제이기 때문이다.

계속 고민을 해봐도 쉽게 떠오르지 않아 다른 사람의 블로그를 참조해보니, 벽을 가중치로 생각해서 벽의 개수를 이용해 다익스트라 알고리즘을 사용하면 된다는 것이다.

그리고 정말 이렇게 접근하니 쉽게 풀렸다. 와우...그리고 여기서도 우선순위 큐를 사용하였는데(블로그에서는 deque를 사용하여 append와 appendleft 두 가지를 사용하는 방식을 사용하였다.) 큐에다가 (y,x)값만 넣어줘서는 안 된다. 그러면 y값을 기준으로 정렬해버리기 때문에 (dist,y,x) 이렇게 세 값을 넣어줘야 dist 값을 기준으로 정렬이 되어서 탐색하는데 문제가 생기지 않는다.

import sys
import heapq

dx = [1,0,-1,0]
dy = [0,1,0,-1]
INF = int(1e9)
input = sys.stdin.readline
M, N = map(int,input().split())
# (0,0) 부터 (N-1,M-1) 까지로 하자.

maze = []
for _ in range(N):
    a = list(map(int,input().rstrip())) # 개행 문자 없애기
    maze.append(a)  # 이차원 배열 maze 생성.

dist = [[INF] * M for _ in range(N)]

q = []
dist[0][0] = 0
heapq.heappush(q,(dist[0][0],0,0))
while q:
    dd, y, x = heapq.heappop(q)	# 큐에 있는 dist값을 dd라는 변수로 받아줌.
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if 0 <= nx < M and 0<= ny < N:
            if dist[ny][nx] == INF:
                if maze[ny][nx] == 1:  # 벽이 있으면
                    dist[ny][nx] = dist[y][x] + 1
                    heapq.heappush(q,(dist[ny][nx],ny,nx))
                else:
                    dist[ny][nx] = dist[y][x]
                    heapq.heappush(q,(dist[ny][nx],ny,nx))

print(dist[N-1][M-1])