[백준/Python] 14497 주난의 난

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

문제 분석

난이도

골드 4

분류

그래프, 0-1 BFS 또는 다익스트라

문제

문제 풀이

풀이

주난이가 점프를 뛸 때마다 주난이와 이어진 0 주변의 1들이 사라진다고 생각하면 된다. 이것만 보고는 백준의 다른 너비우선탐색 문제들과 했갈릴 수 있지만 더 효율적으로 푸는 방법은 다익스트라이다. 그 이유는 0으로 된 부분을 이동하는데 가중치가 0이고, 1을 0으로 바꾸는데 가중치가 1이 들어가는 그래프로 생각하고 풀어줄 수 있기 때문이다.

위의 설명처럼 가중치가 0또는 1만 존재하기 때문에 0-1 BFS로도 해결이 가능한 문제이다.

다익스트라는 O(ElogV)의 시간복잡도, 0-1 BFS는 O(E+V)의 시간복잡도를 갖는다.

 

소스코드

다익스트라 (400ms)

from sys import stdin
from heapq import heappop,heappush
input=stdin.readline

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

inf=float('inf')

n,m=map(int,input().split())
sy,sx,ey,ex=map(lambda x:int(x)-1,input().split())
arr=[input().rstrip() for i in range(n)]
vi=[[inf]*m for i in range(n)]
vi[sy][sx]=0

q=[(0,sx,sy)]

while q:
    nowv,x,y=heappop(q)
    if vi[y][x]<nowv:
        continue
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if -1<nx<m and -1<ny<n:
            nextv=nowv+(arr[ny][nx]!='0')
            if nextv<vi[ny][nx]:
                heappush(q,(nextv,nx,ny))
                vi[ny][nx]=nextv

print(vi[ey][ex])

0-1 BFS (172ms)

from sys import stdin
from heapq import heappop,heappush
input=stdin.readline

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

inf=float('inf')

n,m=map(int,input().split())
sy,sx,ey,ex=map(lambda x:int(x)-1,input().split())
arr=[input().rstrip() for i in range(n)]
vi=[[inf]*m for i in range(n)]
vi[sy][sx]=0

q=[(0,sx,sy)]

while q:
    nowv,x,y=heappop(q)
    if vi[y][x]<nowv:
        continue
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if -1<nx<m and -1<ny<n:
            nextv=nowv+(arr[ny][nx]!='0')
            if nextv<vi[ny][nx]:
                heappush(q,(nextv,nx,ny))
                vi[ny][nx]=nextv

print(vi[ey][ex])

후기

다익스트라나 0-1 BFS 연습 문제로 되게 좋은 문제라 생각한다.