[20419] 화살표 미로 (Easy) python 파이썬

문제: https://www.acmicpc.net/problem/20419

입력

r, c = 가로, 세로 길이

k = 0, 1(0이면 주문서 없음, 1이면 주문서 있음)

아이디어

k = 0 일때는 도착 할 수 있는지 간단하게 확인하기

k = 1일 때는,

• visited의 크기를 r x c x 4와 같이 정의 한 뒤, 마지막의 위치를 k라 할 때, ( 0: 한 개도 안 씀, 1: 오른쪽 하나 씀, 2: 왼쪽 하나 씀, 3: 왼, 오른 다 씀 )
• 오른쪽을 한 번도 안 쓸 경우, 해당 값을 queue에 넣기
• 왼쪽을 한번도 안 쓸 경우, 해당 값을 queue에 넣기

code

from collections import deque
r, c, k = map(int, input().split())
dxy = [[-1, 0], [0, -1], [1, 0], [0, 1]] # 위, 왼, 아래, 오른쪽
dic = {'U': 0, 'D': 2, 'L': 1, 'R': 3}
maps = []
for _ in range(r):
    maps.append(list(map(lambda x:dic[x], list(input()))))

if k == 0:
    q = deque()
    q.append([0, 0])
    visited = [[False] * c for _ in range(r)]
    visited[0][0] = True
    while q:
        x, y = q.popleft()
        d = maps[x][y]
        nx, ny = x + dxy[d][0], y + dxy[d][1]
        if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
            q.append([nx, ny])
            visited[nx][ny] = True

    if visited[-1][-1]:
        print('Yes')
    else:
        print('No')
else:
    q = deque()
    q.append([0, 0, 0])
    # 0: 한 개도 안 씀, 1: 오른쪽 하나 씀, 2: 왼쪽 하나 씀, 3: 왼, 오른 다 씀
    visited = [[[False] * 4 for _ in range(c)] for _ in range(r)]
    visited[0][0][0] = True
    while q:
        x, y, k = q.popleft()
        d = maps[x][y]
        nx, ny = x + dxy[d][0], y + dxy[d][1]
        # 이어서 할 경우
        if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny][k]:
            q.append([nx, ny, k])
            visited[nx][ny][k] = True

        # 왼쪽꺼 쓰지 않은 경우
        if k & 1 == 0:
            nk = k | 1
            nd = (d + 1) % 4
            nx, ny = x + dxy[nd][0], y + dxy[nd][1]
            if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny][nk]:
                q.append([nx, ny, nk])
                visited[nx][ny][nk] = True
        # 오른쪽 꺼 쓰지 않은 경우
        if k & 2 == 0:
            nk = k | 2
            nd = (d - 1) % 4
            nx, ny = x + dxy[nd][0], y + dxy[nd][1]
            if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny][nk]:
                q.append([nx, ny, nk])
                visited[nx][ny][nk] = True
    
    if set(visited[-1][-1]) == {False}:
        print('No')
    else:
        print('Yes')