[백준 1726] 로봇

1. 문제

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

1726번: 로봇

2. 접근 방법

문제 추천 받아서 풀었는데, 굉장히 삼성틱한 문제입니다.

 

이 문제에서 유의해야할 점은 4가지라고 생각합니다.

1. 최대 3칸까지 한 번에 갈 수 있다는 점

2. 회전이 존재한다.

3. 방향 회전 및 이동이 아니라 회전, 이동이 각각 한 번의 명령이라는 점

4. 1회 회전시 시계, 반시계 방향으로 1번만 회전할 수 있다는 점

 

1번이 유의해야할 점인 이유는 다음과 같습니다.

이 문제에서 좌표의 상태는 아래와 같이 3개로 나눌 수 있습니다.

O: 해당 좌표의 값이 0이고(로봇이 이동 가능), 현재 visit하지 않은 좌표

V: 해당 좌표의 값이 0이지만, 현재 visit한 좌표

X: 해당 좌표의 값이 1인 곳

 

현재 로봇의 방향이 →라고 가정해보겠습니다.

[1]. 첫번째 상황

`로봇 O O O`

이 경우에는 로봇이 한 칸, 두 칸, 세 칸 모두 이동 가능합니다.

[2]. 두번째 상황

`로봇 O X O`

이 경우에는 로봇이 한 칸 밖에 이동하지 못합니다.

[3]. 세번째 상황

`로봇 V V O`

이 경우에는 로봇이 세 칸 이동 가능합니다.

 

이러한 경우의 수를 생각했지만, 위에서 언급한 [2], [3]의 경우를 나누지 못하면 .. 7%~8%에서 틀릴 것입니다.

알고 싶지 않았는데 .. 알아버렸습니다 (ノへ￣、)

 

2번이 유의해야할 점인 이유는 다음과 같습니다.

2차 배열에 방향이 들어가게 되면 3차 배열을 사용해야하기 때문이죠

 

다음과 같은 3가지 경우가 있습니다.

각각의 경우는 2번째 줄 맨 오른쪽 요소로 가게 된다는 점에서는 동일한데요, 그 동안 온 행적이 다릅니다.

결국 각각 다른 경우죠

O O O 로봇(↓)
O O O #
O O O O

O O O O
O O O #
O O O 로봇(↑)

 

O O O O
O O 로봇(→) #
O O O O

하지만 방향성이 존재하지 않으면 위의 세가지 경우는 동일한 경우가 됩니다.

그래서 3차 배열을 쓰는 것입니다 !! 경우의 수 기준이 (y좌표, x좌표, 방향) 이기 때문이죠

 

3번이 유의해야할 점인 이유는 회전과 이동을 각각의 경우로 나눠서 생각해야하기 때문ㅇ비니다.

4번이 유의해야할 점인 이유는 현재 방향을 기준으로 시계방향, 반시계 방향으로 90도만 회전할 수 있으므로 변경되는 방향이 현재 방향에 따라 다르기 때문입니다.

3. 코드

python

from collections import deque

Y, X = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(Y)]
start_y, start_x, start_dir = map(int, input().split())
end_y, end_x, end_dir = map(int, input().split())
start_y, start_x, end_y, end_x = start_y - 1, start_x - 1, end_y - 1, end_x - 1
start_dir, end_dir = start_dir % 4, end_dir % 4
RIGHT_TURN = [1, 3, 0, 2]
LEFT_TURN = [2, 0, 3, 1]
dir_x = [0, 1, -1, 0]
dir_y = [-1, 0, 0, 1]

def can_move(x, y):
    if 0 <= x < X and 0 <= y < Y and board[y][x] == 0:
        return True
    return False

visited = [[[False]*4 for _ in range(X)] for _ in range(Y)]

q = deque()
q.append([0, start_x, start_y, start_dir])
visited[start_y][start_x][start_dir] = True
while q:
    now_cnt, now_x, now_y, now_dir = q.popleft()
    if (now_x, now_y, now_dir) == (end_x, end_y, end_dir):
        print(now_cnt)
        break
    for step in range(1, 4):
        test_x, test_y = now_x + dir_x[now_dir] * step, now_y + dir_y[now_dir] * step
        if can_move(test_x, test_y):
            if not visited[test_y][test_x][now_dir]:
                q.append([now_cnt+1, test_x, test_y, now_dir])
                visited[test_y][test_x][now_dir] = True
        else:
            break
    for direction in ['right', 'left']:
        test_dir = RIGHT_TURN[now_dir] if direction == 'right' else LEFT_TURN[now_dir]
        if not visited[now_y][now_x][test_dir]:
            q.append([now_cnt+1, now_x, now_y, test_dir])
            visited[now_y][now_x][test_dir] = True

4. 마치며

위의 코드에서는 direction을 명시적으로 right, left로 넣어주느라 저렇게 넣었는ㄷㅔ요

그냥 dictionary로 해서 갈 수 있는 방향의 idx를 리스트로 담아줘도 좋겠네요.

 

여튼 무튼 읽어주셔서 감사합니다