격자 board의 각 통행 가능한 칸에는 U·D·L·R 안내 방향이 하나 있어요. #은 들어갈 수 없는 벽이에요. 한 번 이동하면 인접한 위·아래·왼쪽·오른쪽 칸으로 가며, 원래는 현재 칸의 안내 방향으로만 이동할 수 있어요. 전체 이동 중 최대 한 번은 현재 칸의 안내를 무시하고 원하는 인접 방향으로 이동할 수 있어요. 수정권을 꼭 쓸 필요는 없어요.
solution(board, start, goal)이 start에서 goal까지의 최소 이동 횟수를 반환하도록 작성해 주세요. 격자 밖이나 벽으로 이동할 수 없으며 도달할 수 없으면 -1이에요. 출발과 도착이 같으면 0이에요.
매개변수와 반환값
- 행·열 수는 각각 1~8, 각 문자열은 해당 열 수만큼의 UDLR#로 구성돼요.
- start와 goal은 각각
[행, 열]이며 범위 안의 벽이 아닌 칸이에요. 좌표는 0부터 시작해요. - 반환값은 최소 이동 횟수 또는 -1인 정수예요.
예시
board = ['RRD', 'UUL'],start = [0, 0],goal = [1, 0]이면 결과는1이에요.board = ['RR', 'UU'],start = [0, 0],goal = [1, 1]이면 결과는2이에요.
실행용 입출력
첫 줄에 rows cols, 다음 rows줄에 격자 문자열, 마지막 줄에 start_row start_col goal_row goal_col을 입력해요. 결과 하나를 출력해요.
예시 입력
2 3 RRD UUL 0 0 1 0
예상 결과
1
예시 입력
2 2 RR UU 0 0 1 1
예상 결과
2
핵심 개념
bfs-grid: 한 이동의 비용이 모두 1이면 너비 우선 탐색으로 가까운 상태부터 확인해 최소 이동 횟수를 구할 수 있어요.graph-basic: 같은 칸이라도 수정권을 남긴 상태와 이미 쓴 상태는 이후 가능한 이동이 달라요. 방문 여부에(행, 열, 사용 여부)를 함께 저장해요.array-2d:board[r][c]는 현재 칸의 문자예요. 이동하기 전에 격자 범위와 벽 여부를 확인해요.
collections.deque는 앞에서 꺼내고 뒤에 넣는 큐예요. .popleft()로 먼저 들어온 항목을 꺼내고 .append(...)로 뒤에 추가해요. 튜플은 좌표·상태를 묶고 집합은 중복 방문을 막아요. int(condition)은 참을 1, 거짓을 0으로 바꿔 수정권 소비를 계산할 수 있어요. continue는 이번 후보 이동을 건너뛰어요. 표준 라이브러리이며 외부 패키지가 아니에요.
깊이 우선 탐색은 연결된 경로를 따라 도달 여부를 확인해요. 여기서는 최소 이동 횟수가 필요해 가까운 상태부터 확인해요. 시작 상태를 거리 0으로 큐에 넣고, 꺼낸 상태의 새 이웃을 거리+1로 큐 뒤에 넣어요. 먼저 들어온 상태를 먼저 꺼내는 FIFO 순서 덕분에 거리 0·1·2 순으로 처리돼요. 모든 이동이 1회이므로 같은 (행,열,사용 여부)를 처음 발견한 거리가 그 상태의 최단거리예요.
입력 하네스의 input()은 한 줄의 문자열을 읽고, .split()은 공백으로 항목을 나눠요. map(int, ...)는 각 항목을 정수로 바꾸고 list(...)는 그 결과를 리스트로 모아요. range(n)은 0부터 n-1까지 반복해요. 하네스는 함수 호출을 위한 자체 연결이며 풀이의 반환 계약과 구분해요.