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

문제풀이 아이디어

n,m 이 비교적 작고 뭔가 확실히 정해지지 않은 문제들은 완전탐색으로 풀리는 경우가 많다.
언제 회전할 지 모르면 왼쪽으로 회전, 오른쪽으로 회전한 경우를 둘다 넣고, 앞으로 몇 칸 직진할 지 모르면 가능한 경우 다 해본다.
이때 deque나 재귀함수 인자로 count+1를 넘겨주면서 연산횟수를 센다.

[다른 문제와 차이점]

• 주어진 좌표로 이동뿐만 아니라 바라보는 방향까지 맞춰야 한다.
• 이동할 수 있는 칸 수가 1~3칸으로 유동적이다.
• 언제 회전할 지 모른다.

[알고리즘]
1. 어느 좌표로 이동했을 때 어느 방향에서 이동했는 지에 따라 다르기 때문에
동, 서, 남, 북을 포함한 3차원 배열로 방문 체크
2. (x, y, 방향, 몇번의 연산으로 이동했는지)를 큐에 담는다.
3. 바라보는 방향으로 직진했을 때 1~3칸까지 가능한만큼 큐에 넣는다.
4. 제자리에서 방향만 바꿔 큐에 넣는다.

풀이코드

from collections import deque
n, m = map(int, input().split())
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))

now_x, now_y, now_dir = map(int, input().split())
target_x, target_y, target_dir = map(int, input().split())


def turnLeft(dir):
    if dir == 1:
        dir = 4
    elif dir == 3:
        dir = 1
    elif dir == 2:
        dir = 3
    else:
        dir = 2
    return dir

def turnRight(dir):
    if dir == 1:
        dir = 3
    elif dir == 4:
        dir = 1
    elif dir == 2:
        dir = 4
    else:
        dir = 2
    return dir


dx = [0, 0, 1, -1] # 동 서 남 북 : 1, 2, 3, 4
dy = [1, -1, 0, 0]


def bfs(now_x, now_y, now_dir):
    queue = deque()
    visited = [[[0 for _ in range(5)] for _ in range(m)] for _ in range(n)]
    visited[now_x][now_y][now_dir] = 1
    queue.append((now_x, now_y, now_dir, 0))
    while queue:
        x, y, dir, count = queue.popleft()
        if x == target_x-1 and y == target_y-1 and dir == target_dir:
            return count
        
        # 직진
        for i in range(1, 4):
            mx = x + (dx[dir-1] * i)
            my = y + (dy[dir-1] * i)

            if 0 <= mx < n and 0 <= my < m and data[mx][my] == 0:
                if visited[mx][my][dir] == 0:
                    visited[mx][my][dir] = 1
                    queue.append((mx, my, dir, count+1))
            else:
                break

        # 회전
        left = turnLeft(dir)
        right = turnRight(dir)
        if visited[x][y][left] == 0:
            visited[x][y][left] = 1
            queue.append((x, y, left, count+1))
        if visited[x][y][right] == 0:
            visited[x][y][right] = 1
            queue.append((x, y, right, count+1))

print(bfs(now_x-1, now_y-1, now_dir))

회고

어려운 문제들은 대부분 방향값을 따로 주면서 이동에 제약을 준다.
방향값도 동서남북이 기준일 때도 있고, 북쪽을 기준을 시계방향일 때도 있다보니 문제를 잘 읽고 자신이 헷갈리지 않는 순서로 바꾸는 것도 하나의 방법인 것 같다.
방향을 두번꼬아서 생각하니까 동쪽이랑 서쪽을 헷갈려서 1시간동안 맞왜틀하고있었다.

그리고 처음에 DFS로 풀다가 BFS로 바꿨다. DFS로 먼저 접근한 이유는 입력값과 달라진 데이터에서 탐색을 돌려 답을 찾는 문제들을 풀다보니 이것도 DFS로 풀어야겠다고 생각했다.

근데 이 문제에선 사실 맵의 정보가 바뀌지 않아서 굳이 재귀를 돌릴 필요는 없었다. 재귀는 아직도 생각하기 쉽지 않고, 잘못 짰을 때 무한루프 도는 경우가 많아 테스트가 어려워서 연습이 더 필요한 것 같다😂