[백준 18224번] 미로에 갇힌 건우(파이썬)

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

18224번: 미로에 갇힌 건우

bfs문제 중에서

'조건'이 정말 까다롭게 붙은 유형.

이 문제를 봤을 때 가장 어려운 부분은

'm만큼 이동하면 낮과 밤이 바뀐다'라는 부분.

문제를 잘 읽어보면

이동하는 순간에 바뀝니다.

예를들며 m=2인데

낮 1 이라면

이동하는 순간 2가 되어서

밤 0으로 바뀌는 것.

 

사실 여기까지만 알면 문제가 안풀립니다.

게시판의 반례에 계속 넣어보는데

문제가 안풀렸습니다.

결국 구글링하다가 보니

visited를 4차원으로 둬야했습니다.

nxnxmx2

이렇게 둬야 문제를 풀 수 있었습니다.

이유가 뭘까 생각을 곰곰히 해봤는데

m이 얼마있냐에 다라서

얼마나 더 움직일지가 다 달라졌습니다.

3차원으로 

nxnx2로 구현하다보면

이 부분을 살리지 못합니다.

bfs로 길찾기를 하는데

벽을 2번 넘을 수 있는 상황이라고 가정합니다.

원래라면 넘고 또 넘어야하는데

만약에 해당 지점을 이미 밤에 방문한 상태이면

bfs에서는 '이미 방문한 곳이니깐 가지 말아야겠다'라고 판단해버립니다.

그래서 분명 갈 수 있는 부분이

'이미 갔다왔다'라는 이유로 못가게 되버리고

그래서 갈 수 있는 상황인데도

가지 못하는 경우가 생겼어요.

그래서 4차원으로 구현해주면 이런 부분이 해결되기 때문에 깔끔해집니다.

#백준 18224번 미로에 갇힌 건우
from collections import deque

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


def mov(x,y,d):
    nx=x
    ny=y
    while True:
        nx+=dx[d]
        ny+=dy[d]
        if nx<0 or nx>=N or ny<0 or ny>=N:
            nx-=dx[d]
            ny-=dy[d]
            return nx,ny
        if room[nx][ny]==0:
            return nx,ny


N,M=map(int,input().split())
room=[list(map(int,input().split()))for _ in range(N)]
visited=[[[[False]*2 for _ in range(M)]for _ in range(N)] for _ in range(N)]
q=deque()
q.append([0,0,1,0,0])
visited[0][0][0][0]=True
while q:
    x,y,day,move,su=q.popleft()
    if x==N-1 and y==N-1:
        if su==0:
            sun='sun'
        else:
            sun='moon'
        print(day,sun)
        exit(0)


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

        if nx<0 or nx>=N or ny<0 or ny>=N:
            continue

        #이동하고나서 낮과 밤이 바뀐다
        #but이동중에는 아직 안바뀌는 걸 명시해야함

        #그냥 이동
        if room[nx][ny]==0:
            next_move=move+1
            n_su=su
            next_day=day
            if next_move==M:
                next_move=0
                n_su=n_su+1
            if n_su==2:
                n_su=0
                next_day+=1
            if visited[nx][ny][next_move][n_su]==False:
                q.append([nx,ny,next_day,next_move,n_su])
                visited[nx][ny][next_move][n_su]=True
        #벽을 넘는 경우
        if (su==1)and  room[nx][ny]==1:
            px,py=mov(nx,ny,d)
            if room[px][py]==1:
                continue
            next_move = move + 1
            n_su=1
            next_day=day
            if next_move == M:
                next_move=0
                n_su = 0
                next_day =next_day+1
            if visited[px][py][next_move][n_su]==False:
                q.append([px,py,next_day,next_move,n_su])
                visited[px][py][next_move][n_su]=True


print(-1)

 

어려운 bfs문제를 풀 때마다

무지성으로 길찾기를 했던 제 자신이 부끄러워집니다.

이런 류의 문제를 풀면서

길찾기를 어떻게하면 되는지

스스로 점검하는 것도 좋아보이네요.