백준(BOJ) 18224 미로에 갇힌 건우(Python)

문제 내용

조건

 

BFS 문제.

일반적인 BFS 문제와는 달리 이미 한 번 방문한 노드여도 지금 상태가 낮인지 밤인지, 몇 번 움직인 상태인지에 따라 최단 거리가 달라지는 문제이다. 따라서 일반적인 visited가 아닌, 각 노드에 낮밤과 움직인 횟수를 더 고려하는 visited를 사용해야 BFS를 통해 최단 거리를 구할 수 있었다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,m=map(int,input().split())
L=[list(map(int,input().split())) for i in range(n)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
queue=deque()
queue.append([0,0,0,0,1])
visited=[[[[0 for k in range(11)] for x in range(2)] for i in range(n)] for j in range(n)]
flag=0
visited[0][0][0][0]=1
while queue:
    x,y,a,b,d=queue.popleft()
    if x==y==n-1:
        flag=1
        break
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<n and 0<=ny<n:
            if not L[nx][ny] and not visited[nx][ny][a][b+1]:
                visited[nx][ny][a][b+1]=1
                if b+1==m:
                    if a==0:
                        queue.append([nx,ny,1,0,d])
                    else:
                        queue.append([nx,ny,0,0,d+1])
                else:
                    queue.append([nx,ny,a,b+1,d])
            elif L[nx][ny] and a:
                nx+=dx[i]
                ny+=dy[i]
                flag2=0
                while 0<=nx<n and 0<=ny<n:
                    if not L[nx][ny]:
                        flag2=1
                        break
                    nx+=dx[i]
                    ny+=dy[i]
                if flag2 and not visited[nx][ny][a][b+1]:
                    visited[nx][ny][a][b+1]=1
                    if b+1==m:
                        queue.append([nx,ny,0,0,d+1])
                    else:
                        queue.append([nx,ny,1,b+1,d])
if flag:
    if a==0:
        a='sun'
    else:
        a='moon'
    print(d,a)
else:
    print(-1)

 

visited를 확장하는 문제를 푼 게 이번이 처음은 아닌데, 쉽게 떠올리기는 어려웠다.

모두 고려하기를 해야한다는 것을 눈치챈 순간 뇌정지가 와서 힘들었다.