[Gold III] 1726 - 로봇

문제

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때,  이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

예제 입력 1 복사

5 6
0 0 0 0 0 0
0 1 1 0 1 0
0 1 0 0 0 0
0 0 1 1 1 0
1 0 0 0 0 0
4 2 3
2 4 1

예제 출력 1 복사

9

 

---

# 풀이 방법

최소 명령 횟수를 물어봤기 때문에 bfs로 접근했다.

두가지 부분에서 실수가 있었다

• 명령1: 조건을 한줄로 쓰려다 보니 실수가 있었다. go1부터 안되는거면 go3까지 갈 필요가 없다
• 명령2: 동서남북 오른쪽 90도 회전할 때 규칙을 찾으려고 노력했다. 그런게 없이 그냥 구현하면 되었다

또, cnt를 구해야 할 때는 같이 queue에 넣는 것이 좋다

---

# 코드

<코드2>가 틀린 이유에 대한 gpt 설명

✅ 구체적인 예시 들어볼게

• 1칸 가기, 2칸 가기, 3칸 가기를 각각 시도하는데
• 1칸 이동은 이미 방문한 좌표라고 치자.

<코드1> 흐름

• 1칸 이동: 방문했으면 무시하고 2칸, 3칸 이동 계속 시도함

<코드2> 흐름

• 1칸 이동: 방문한 곳이니까 바로 break (→ 2칸, 3칸 이동도 못함)

결국 <코드2>는 "방문했던 칸이 있다"는 이유만으로 3칸 가는 경우를 아예 시도도 못하고 끊어버리는 거야.

📚 예시로 이해해보자

상황:

• (0,0) 에서 동쪽(오른쪽, d=1)으로 이동 중
• (0,1)은 이미 방문한 곳이야 (다른 경로에서 들렀었어)
• (0,2)는 아직 방문 안 한 곳

질문: (0,0) → (0,1) → (0,2)로 갈 수 있나?

답:

• (0,1)을 "통과"하는 건 문제없어.
• 단, (0,1)에 도착해서 또 "거기서부터 새로 탐색"하는 걸 막을 뿐이야.
• 목표는 (0,2)에 도달하는 거니까 2칸 이동은 정상적으로 할 수 있어.

✅ 요약:

• "이미 방문한 곳을 통과"하는 건 괜찮아.
• "이미 방문한 곳에 다시 도착해서 거기서부터 새 BFS를 하려는 것"만 막는 거야.

import sys
sys.stdin = open("input.txt","r")
from collections import deque

M, N = map(int,sys.stdin.readline().split())
graph = [list(map(int,sys.stdin.readline().split())) for _ in range(M)]
sx,sy,sd = map(int,sys.stdin.readline().split())
tx,ty,td = map(int,sys.stdin.readline().split())

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

def turn_left(d):
    if d == 1: return 4
    elif d == 4: return 2
    elif d == 2: return 3
    elif d == 3: return 1

def turn_right(d):
    if d == 1: return 3
    elif d == 3: return 2
    elif d == 2: return 4
    elif d == 4: return 1

visited = set()
def bfs(x,y,d):
    queue = deque()
    queue.append((x,y,d,0))
    
    while queue:
        x,y,d,cnt = queue.popleft()
        visited.add((x,y,d))

        if (x,y,d) == (tx-1,ty-1,td):
            return cnt
        
        # 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
        for i in range(1,4):
            nx, ny = x + i*dx[d], y + i*dy[d]
            
            # <코드1> -- 정답
            if not (0 <= nx < M and 0 <= ny < N):
                break
            if graph[nx][ny] == 1:
                break
            if (nx,ny,d) not in visited:
                visited.add((nx,ny,d))
                queue.append((nx,ny,d,cnt+1))

            # <코드2> -- 오답
            if 0 <= nx < M and 0 <= ny < N and (nx,ny,d) not in visited and graph[nx][ny] == 0:
                visited.add((nx,ny,d))
                queue.append((nx,ny,d,cnt+1))
            else:
                break

        # 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.
        for func in (turn_left, turn_right):
            new_d = func(d)
            if (x,y,new_d) not in visited:
                visited.add((x,y,new_d))
                queue.append((x,y,new_d,cnt+1))



print(bfs(sx-1,sy-1,sd))

import sys
# sys.stdin = open("input.txt","r")
from collections import deque
# 동1 / 서2 / 남3 / 북4
dx = [None, 0, 0, 1, -1]
dy = [None, 1, -1, 0, 0]

n, m = map(int,sys.stdin.readline().split())
graph = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
sx, sy, sd = map(int,sys.stdin.readline().split())
tx, ty, td = map(int,sys.stdin.readline().split())

visited = set()

def turn_left(d):
    if d == 1: return 4
    elif d == 4: return 2
    elif d == 2: return 3
    elif d == 3: return 1

def turn_right(d):
    if d == 1: return 3
    elif d == 3: return 2
    elif d == 2: return 4
    elif d == 4: return 1

def bfs(x,y,d):
    cnt = 0
    queue = deque()
    queue.append((x,y,d,cnt))

    while queue:
        x, y, d, cnt = queue.popleft()
        visited.add((x,y,d))
        if (x,y,d) == (tx-1,ty-1,td):
            return cnt
        
        # 명령 1. Go k: k는 1, 2 또는 3일 수 있다.
        # 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
        for i in range(1,4):
            nx, ny = x + dx[d] * i, y + dy[d] * i
            if not (0 <= nx < n and 0 <= ny <  m):
                break
            if graph[nx][ny] == 1:
                break
            if (nx,ny,d) not in visited:
                visited.add((nx,ny,d))
                queue.append((nx,ny,d,cnt+1))
        
        # 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.
        # 모든 방향에 대해 회전 해야 함
        # 회전
        for turn_func in (turn_left, turn_right):
            nd = turn_func(d)
            if (x, y, nd) not in visited:
                visited.add((x,y,nd))
                queue.append((x, y, nd, cnt + 1))

print(bfs(sx-1,sy-1,sd))

---

# 참고 (런타임 오류 해결)

미완성코드.. 첫 시도

# 2025-04-13 04:51-05:30
import sys
from collections import deque
sys.stdin = open("input.txt","r")
m, n = map(int,sys.stdin.readline().split())
graph = [list(map(int,sys.stdin.readline().split())) for _ in range(m)]
r1,c1,d1 = map(int,sys.stdin.readline().split())
r2,c2,d2 = map(int,sys.stdin.readline().split())

# 동 서 남 북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(x,y,d):
    visited = [[[False]*4 for _ in range(n)] for _ in range(m)]
    cnt = 0

    queue = deque()
    queue.append((x,y,d,cnt))
    visited[x][y][d] = True # 방문 처리

    while queue:
        x, y, d, cnt = queue.popleft()
        # print((x,y,d, cnt))
        if x == r2-1 and y == c2-1 and d == d2-1: # 목적지에 도착했을 경우 종료
            return cnt
        
        # 명령1: go k(=1,2,3)
        for i in range(1,4):
            nx, ny = x + dx[d]*i, y + dy[d]*i
            if 0 <= nx < m and 0 <= ny < n:
                if graph[nx][ny] == 1:
                    break
                if not visited[nx][ny][d]:
                    visited[nx][ny][d] = True
                    queue.append((nx,ny,d,cnt+1))
            else:
                break
        
        # 명령2: turn dir (left, right) 90도
        d_left = (d + 3) % 4
        if not visited[x][y][d_left]:
            visited[x][y][d_left] = True 
            queue.append((x,y,d_left,cnt+1))
        
        d_right = (d + 1) % 4
        if not visited[x][y][d_right]:
            visited[x][y][d_right] = True 
            queue.append((x,y,d_right,cnt+1))

        # print(f'graph[{x}][{y}] = {graph[x][y]}')

print(bfs(r1-1,c1-1,d1-1))