[Baekjoon] 백준 1261 알고스팟 (G5^ / 다익스트라) - Python

링크

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

1261번: 알고스팟

 

 

 

 

문제 해석

미로의 크기는 N * M

미로는 빈 방(0) 또는 벽(1)으로 이루어져 있음
벽은 부술 수 있으며, 부수지 않으면 해당 칸으로 이동할 수 없음
이동은 상하좌우로 이동 가능

(1,1)에서 (N, M)으로 이동하기 위해서 최소 몇 개의 벽을 부셔야 하는가?

 

 

 

 

풀이 & 코드 해석

문제를 해결하기 위해서 먼저 DFS 방식으로 풀어보았습니다.

def dfs(x, y):
    if x == n - 1 and y == m - 1:
        return

    for d in range(4):
        nx = dx[d] + x
        ny = dy[d] + y

        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue

        # 다음 위치가 벽인 경우
        if arr[nx][ny] == 1:
            if dp[nx][ny] > dp[x][y] + 1:
                dp[nx][ny] = dp[x][y] + 1
                dfs(nx, ny)

        # 다음 위치가 빈방인 경우
        if arr[nx][ny] == 0:
            if dp[nx][ny] > dp[x][y]:
                dp[nx][ny] = dp[x][y]
                dfs(nx, ny)

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

m, n = map(int, input().split())

dp = [[int(1e9)] * m for i in range(n)]

arr = []

for i in range(n):
    arr.append(list(map(int, input().strip())))

dp[0][0] = 0
dfs(0, 0)

print(dp[n - 1][m - 1])

 

값은 제대로 출력되었지만,

N과 M의 최대 크기가 100이므로 배열의 최대 크기는 10000이 되고,

DFS의 시간 복잡도는 O(V + E)이므로 시간초과가 날 수 밖에 없는 상황이었습니다.

 

 

다익스트라를 이용하면 문제를 해결할 수 있습니다.

 

 

 

 

코드

import heapq

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

m, n = map(int, input().split())

dist = [[int(1e9)] * m for i in range(n)]

arr = []

for i in range(n):
    arr.append(list(map(int, input().strip())))


dist[0][0] = 0
q = []
heapq.heappush(q, (0, (0, 0)))

while(q):
    now_dist, xy = heapq.heappop(q)
    x, y = xy

    if dist[x][y] != now_dist:
        continue

    for d in range(4):
        nx = dx[d] + x
        ny = dy[d] + y
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue

        # 다음 위치가 벽인 경우
        if arr[nx][ny] == 1:
            if dist[nx][ny] > dist[x][y] + 1:
                dist[nx][ny] = dist[x][y] + 1
                heapq.heappush(q, (dist[nx][ny], (nx, ny)))

        # 다음 위치가 빈방인 경우
        if arr[nx][ny] == 0:
            if dist[nx][ny] > dist[x][y]:
                dist[nx][ny] = dist[x][y]
                heapq.heappush(q, (dist[nx][ny], (nx, ny)))

print(dist[n - 1][m - 1])

 

 

 

 

발생한 문제 & 해결 방안

0과 1의 가중치를 가지는 문제가 나오면 다익스트라를 의심해볼만 하다.

 

문제를 풀기 전 시간복잡도를 생각해보자.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java