[백준] [BFS] 16954. 움직이는 미로 탈출

16954. 움직이는 미로 탈출

16954번: 움직이는 미로 탈출

 

• 내 풀이
  • 위로 올라가는 큐값들 외에 아래에서 머물던 큐값이 돌면서 막히면 return 0 하고 끝나버리는 문제
    • -> 이후에 큐가 없을때만 종료하도록 not queue 넣고 해결
  • cnt값을 체크해서 바로 위가 벽이 내려가면서 생긴 뚫린 곳들이면 바로 가능하다고 판단하고 종료
    • -> 시간 단축

#사용했던 반례

..###.##
##...#.#
..#.#..#
#.#...#.
.#...#.#
.#.#..##
#..#..#.
..#....#


#결과
1

from collections import deque

def down(cnt,graph):
    cnt+=1
    tmp=graph[:]
    tmp.insert(0, ['.' for _ in range(8)])
    tmp.pop()
    return (cnt,tmp)

def solve():
    x,y=7,0

    queue.append((x,y,graph,0))

    while queue:
        x,y,gp,c=queue.popleft()

        if (c and c >= x) or (x==0 and y==7):
            print(1)
            return


        cnt,tmp=down(c,gp)
        flag=0
        for i in range(9):
            nx=x+dx[i]
            ny=y+dy[i]
            if i==8 and flag:
                continue

            if nx<0 or nx>=8 or ny<0 or ny>=8: continue
            if gp[nx][ny]=='#': continue

            if tmp[nx][ny]!='#':
                flag=1
                queue.append((nx,ny,tmp,cnt))


        if flag==0 and not queue:
            print(0)
            return



graph=[list(input().rstrip()) for _ in range(8)]
dx=[-1,1,0,0,1,1,-1,-1,0]
dy=[0,0,-1,1,1,-1,1,-1,0]


queue=deque()
solve()

 

 

• 다른사람 풀이
  • 같은 위치에서 넣어진 큐값들 길이만큼 while문 내의 for문 돌면서 체크 
    • -> 그 큐값들끼리만 visited 확인할 수 있음
    • 다음 레벨에서는 갔던 곳 또 갈수 있으므로 while문 내에서 visited 초기화

#남곤님 풀이
import sys
from collections import deque

input = sys.stdin.readline

dx = (1, 1, 0, -1, -1, -1, 0, 1, 0)
dy = (0, 1, 1, 1, 0, -1, -1, -1, 0)


def bfs():
    sy, sx = 7, 0
    dest_y, dest_x = 0, 7

    que = deque()
    que.append((sy, sx))

    while True:
        visited = [[False] * 8 for _ in range(8)]

        length = len(que)

        if length == 0:
            break

        #같은 레벨에서 나온 큐들끼리만 for문 내에서 처리 -> 그 큐값들끼리만 visited 확인
        for _ in range(length):
            y, x = que.popleft()

            if board[y][x] == "#":
                continue

            for i in range(9):
                ny = y + dy[i]
                nx = x + dx[i]
                if 0 <= ny < 8 and 0 <= nx < 8 and board[ny][nx] == "." and not visited[ny][nx]:
                    visited[ny][nx] = True
                    que.append((ny, nx))

                    if (ny, nx) == (dest_y, dest_x):
                        return 1

        for i in range(7, 0, -1):
            board[i] = board[i - 1]
        board[0] = ["."] * 8

    return 0


board = [list(input().strip()) for _ in range(8)]

print(bfs())