[Algorithm🧬] 정올 1238 : 미로탈출 로봇중간 단계

문제

import sys
from collections import deque

readl = sys.stdin.readline

def BFS():
    q = deque([(1, 1)])
    지도[1][1] = 2 # 장애물은 1로 체크, 방문은 2로 체크

    cnt = 0

    i = 0

    while q:
        x, y = q.popleft()
        # print(x, y)
        dx, dy = move[방향[i % 4]]
        nx, ny = x + dx, y + dy

        if not 0 <= nx <= n + 1:
            continue
        if not 0 <= ny <= n + 1:
            continue

        # 가는 도중에 방문한 길을 만나면 거기서 끝
        if 지도[nx][ny] == 2:
            break

        # 장애물을 만나면 방향을 틀어야함.
        if 지도[nx][ny] == 1:
            # 한번 틀고,
            i += 1
            dx, dy = move[방향[i % 4]]

            # 갔던 길인지 체크
            if 지도[x + dx][y + dy] == 2:
                break

            # 벽이면 다시 틀어본다.
            breaked = False
            while 지도[x + dx][y + dy] == 1:
                i += 1
                dx, dy = move[방향[i % 4]]

                if 지도[x + dx][y + dy] == 2:
                    breaked = True
                    break

            if breaked:
                break


            # 가능하면 틀어진 방향을 큐에 넣는다.
            q.append((x + dx, y + dy))
            지도[x + dx][y + dy] = 2
            cnt += 1
            continue

        지도[nx][ny] = 2
        q.append((nx, ny))
        cnt += 1

    return cnt



n = int(readl())
지도 = [[1] + list(map(int, [c for c in readl().strip()])) + [1] if 1 <= i <= n else [1] * (n + 2) for i in range(n + 2)]
방향 = [i - 1 for i in list(map(int, readl().split()))]
move = [(1, 0), (0, -1), (-1, 0), (0, 1)]

# ch = [[0] * (n + 2) for _ in range(n + 2)]

print(BFS())

큐를 쓰지 않는 코드

def BFS():
    ch[1][1] = 1

    cnt = 0
    i = 0
    회전 = 0
    x, y = 1, 1
    while True:
        dx, dy = move[방향[i % 4]]
        nx, ny = x + dx, y + dy

        if 1 <= nx <= n and 1 <= ny <= n and 지도[nx][ny] == 0:
            회전 = 0

            # 가는 도중에 방문한 길을 만나면 거기서 끝
            if ch[nx][ny] == 1:
                break

            ch[nx][ny] = 1
            x, y = nx, ny
            cnt += 1
        else:
            i += 1
            회전 += 1
            # 틀 수 있는 4 방향 다 틀어봄.
            # 근데 3인 이유는 4번 틀어봤자 4번째 튼건 내가 온 방향이라
            if 회전 > 3:
                break

    return cnt
    
ch = [[0] * (n + 2) for _ in range(n + 2)]