[백준1726/골드3] 로봇 - Python

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

 

 

✅ 문제 조건

 

1. 전진 명령 : 1~3칸 전진 가능

2. 회전 명령 : 오른쪽 또는 왼쪽으로 90도 회전 가능

3. 시작위치와 시작방향, 도착 위치와 도착 방향이 주어진다

4. 몇번의 명령으로 도착지점에 도착할 수 있는지 출력

 

 

✅ 접근 방법

일단 방향까지 필요한 문제이기 때문에 [세로][가로][방향]을 가지는 3차원 visited 배열을 만들어야한다.

그리고 1. 전진 명령을 할 경우와 2. 회전 명령을 할 경우를 나눠서 명령시행을 반복한다.

최종 도착과 맞는 위치와 방향일 경우 break

 

 

✅ 구현

 

1. 전진 명령

# 전진
for k in range(1, 4):
    nr, nc = cr + direction[cd][0] * k, cc + direction[cd][1] * k

    if not (0 <= nr < M and 0 <= nc < N) or mp[nr][nc]:
        break
    if visited[nr][nc][cd]:
        continue
    visited[nr][nc][cd] = True
    q.append((nr, nc, cd, cnt + 1))

 

여기서 한칸 이동했을때, 앞이 벽으로 막혀있으면 그 뒤에 두칸이동과 세칸 이동도 불가능하므로 벽이 나타났을 경우 바로 break 해줘야한다.

처음에 이걸 따로 처리해주지 않아서 (벽을 뚫고 통과해서) 출력 값이 정답보다 작게 나왔다.

 

 

2. 회전 명령

direction = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 오른쪽, 왼쪽, 아래, 위
next_direction = [(2, 3), (2, 3), (0, 1), (0, 1)]

# 회전
for nd in next_direction[cd]:
    if not visited[cr][cc][nd]:
        visited[cr][cc][nd] = True
        q.append((cr, cc, nd, cnt + 1))

 

문제에 주어진 방향이 시계방향으로 회전이 아니라 왼쪽 오른쪽 아래 위 순서로 주어져서 따로 다음방향을 설정해줘야한다.

 

 

✅ 정답 코드

'''
go k: 현재 방향으로 1, 2, 3 칸만큼 이동
turn dir: 왼쪽, 오른쪽으로 회전
'''

from collections import deque

M, N = map(int, input().split())  # 세로, 가로
mp = [list(map(int, input().split())) for _ in range(M)]
sr, sc, sd = map(int, input().split())
er, ec, ed = map(int, input().split())
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 오른쪽, 왼쪽, 아래, 위
next_direction = [(2, 3), (2, 3), (0, 1), (0, 1)]

visited = [[[False] * 4 for _ in range(N)] for _ in range(M)]
visited[sr-1][sc-1][sd-1] = True
q = deque([(sr-1, sc-1, sd-1, 0)])

while q:
    cr, cc, cd, cnt = q.popleft()

    if (cr, cc, cd) == (er-1, ec-1, ed-1):
        print(cnt)
        break

    # 전진
    for k in range(1, 4):
        nr, nc = cr + direction[cd][0] * k, cc + direction[cd][1] * k

        if not (0 <= nr < M and 0 <= nc < N) or mp[nr][nc]:
            break
        if visited[nr][nc][cd]:
            continue
        visited[nr][nc][cd] = True
        q.append((nr, nc, cd, cnt + 1))

    # 회전
    for nd in next_direction[cd]:
        if not visited[cr][cc][nd]:
            visited[cr][cc][nd] = True
            q.append((cr, cc, nd, cnt + 1))

 

 

그냥 문제에 나온대로 옮겨써서 구현하는 문제였다.