문제 보기 · Level 3 · 2020 KAKAO BLIND RECRUITMENT · 정답률 28% · 푼 사람 4,943명 (2026-09-30 기준)1
문제
N×N 지도(0은 빈칸, 1은 벽)에서 2×1 크기 로봇이 (1, 1), (1, 2)에 가로로 놓여 있다. 왼쪽 위가 (1, 1)이다. 로봇은 1초에 한 번 상하좌우로 한 칸 옮기거나, 차지한 두 칸 중 하나를 축으로 90도 돈다. 돌 때는 도착할 칸과, 돌면서 쓸고 지나가는 대각선 칸이 모두 비어 있어야 한다. 로봇의 두 칸 중 하나라도 (N, N)에 닿는 최소 시간을 돌려준다.
- 5 ≤ N ≤ 100
- 항상 도착할 수 있다
풀이
막히면 한 단계씩 펼친다.
필요한 개념
너비 우선 탐색(BFS): 모든 동작이 1초라 최소 시간은 BFS의 최단 거리다. 점은 칸 하나가 아니라 “로봇이 차지한 두 칸”이다.
1단계 · 작은 예로 손으로 풀기
로봇이 (1, 1), (1, 2)에 가로로 있다. 할 수 있는 동작은 이렇다.
- 옮기기: 두 칸을 같은 방향으로 한 칸씩. 아래로 옮기면 (2, 1), (2, 2)다. 두 칸 모두 비어 있어야 한다.
- 돌기: (1, 1)을 축으로 아래로 돌면 (1, 2)가 (2, 1)로 간다. 돌면서 (2, 2)를 쓸고 지나간다. 그래서 (2, 1), (2, 2)가 모두 비어 있어야 한다. (1, 2)를 축으로 아래로 돌 때도 (2, 2)로 가며 (2, 1)을 쓸고 지나가니, 필요한 빈칸이 똑같다.
즉 가로 로봇은 “바로 아래 두 칸(또는 바로 위 두 칸)이 비었나”만 보면, 두 칸 각각을 축으로 도는 두 가지 동작이 모두 된다. 세로 로봇은 “바로 왼쪽 두 칸(또는 오른쪽 두 칸)”을 본다.
돌기는 축 A에서 B로 가는 벡터 B − A를 회전 행렬로 90도 돌린 뒤 A를 다시 더한 것이다. 위의 예에서 (1, 2) − (1, 1) = (0, 1)을 돌리면 (1, 0)이고, (1, 1)을 더하면 (2, 1)이다.
2단계 · 가장 단순한 방법과 그 속도
동작 순서를 모두 만들어 보면 한 번에 동작이 최대 8가지라 t초면 8ᵗ가지다. 답이 수십 초만 되어도 어림없다. 하지만 로봇이 놓일 수 있는 상태는 많아야 가로 N(N − 1)개 + 세로 N(N − 1)개, N = 100이면 19,800개뿐이다. 상태마다 한 번씩만 보면 된다.
3단계 · 핵심 아이디어
- 상태 = 두 칸: 로봇을 ((r1, c1), (r2, c2))로 나타내고, 두 칸을 늘 정렬해 둔다. 같은 위치를 “앞뒤만 바꾼” 두 이름으로 따로 세지 않기 위해서다. (a, b)와 (b, a)를 한 묶음(동치류)으로 보면, 정렬한 튜플은 그 묶음을 대표하는 이름이다.
- BFS: 모든 동작이 1초이니 상태를 점, 동작을 간선으로 보고 BFS를 한다. 처음으로 (N, N)을 포함하는 상태를 꺼낸 순간의 거리가 답이다.
- 벽 두르기: 지도 둘레를 1(벽)로 한 겹 감싸면 범위 검사 없이 “벽이 아니면 간다”만 보면 된다. 감싸면 칸 번호가 1부터가 되어 문제의 좌표와 같아진다.
4단계 · 코드 흐름
- 지도를 벽으로 한 겹 감싼다.
- 상태에서 갈 수 있는 다음 상태를 만드는 함수를 짠다: 옮기기 4가지, 돌기(가로면 위·아래, 세로면 왼쪽·오른쪽마다 2가지).
- 시작 상태 ((1, 1), (1, 2))를 거리 0으로 큐에 넣고 BFS를 한다. 거리는 딕셔너리에 적는다.
- 꺼낸 상태에 (N, N)이 있으면 그 거리를 돌려준다.
5단계 · 파이썬 코드
from collections import deque
def solution(board):
N = len(board)
B = [[1] * (N + 2)] + [[1] + row + [1] for row in board] + [[1] * (N + 2)]
def nexts(a, b):
(r1, c1), (r2, c2) = a, b
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): # 옮기기
if B[r1 + dr][c1 + dc] == 0 and B[r2 + dr][c2 + dc] == 0:
yield tuple(sorted(((r1 + dr, c1 + dc), (r2 + dr, c2 + dc))))
if r1 == r2: # 가로 → 세로
for d in (-1, 1):
if B[r1 + d][c1] == 0 and B[r2 + d][c2] == 0:
yield tuple(sorted(((r1, c1), (r1 + d, c1))))
yield tuple(sorted(((r2, c2), (r2 + d, c2))))
else: # 세로 → 가로
for d in (-1, 1):
if B[r1][c1 + d] == 0 and B[r2][c2 + d] == 0:
yield tuple(sorted(((r1, c1), (r1, c1 + d))))
yield tuple(sorted(((r2, c2), (r2, c2 + d))))
start = ((1, 1), (1, 2))
dist = {start: 0}
q = deque([start])
while q:
a, b = q.popleft()
if (N, N) in (a, b):
return dist[(a, b)]
for nxt in nexts(a, b):
if nxt not in dist:
dist[nxt] = dist[(a, b)] + 1
q.append(nxt)
yield: 함수가 값을 하나씩 내놓게 한다.for nxt in nexts(a, b)가 그 값을 차례로 받는다. 리스트를 만들어 돌려주는 것과 같은 일을 한다.tuple(sorted(...)): 두 칸을 정렬해 튜플로 만든다. 튜플이라 딕셔너리의 열쇠로 쓸 수 있다.[1] + row + [1]: 각 줄 양 끝에 벽을 붙인다.
6단계 · 실행 추적
board = [[0,0,0,1,1],[0,0,0,1,0],[0,1,0,1,1],[1,1,0,0,1],[0,0,0,0,0]]
BFS가 찾은 최단 경로 하나(좌표는 문제처럼 1부터):
| 시간 | 로봇 위치 | 동작 |
|---|---|---|
| 0 | (1, 1), (1, 2) | 시작 |
| 1 | (1, 2), (1, 3) | 오른쪽으로 옮기기 |
| 2 | (1, 3), (2, 3) | (1, 3)을 축으로 돌기 |
| 3 | (2, 3), (3, 3) | 아래로 옮기기 |
| 4 | (3, 3), (4, 3) | 아래로 옮기기 |
| 5 | (4, 3), (5, 3) | 아래로 옮기기 |
| 6 | (5, 3), (5, 4) | (5, 3)을 축으로 돌기 |
| 7 | (5, 4), (5, 5) | 오른쪽으로 옮기기, 도착 |
답은 7이다. 문제 설명의 경로와 같다.
7단계 · 복잡도와 흔한 실수
상태가 많아야 약 2N²개이고 상태마다 다음 상태가 8개 이하라 \(O(N^2)\)다. 100×100에서도 금방 끝난다.
- 로봇의 두 칸을 정렬하지 않아 같은 위치를 두 번 세고, 방문 표시가 어긋난다.
- 돌 때 쓸고 지나가는 대각선 칸을 확인하지 않는다.
- 한 칸을 축으로 도는 것만 넣고, 다른 칸을 축으로 도는 것을 빠뜨린다.
- “두 칸 중 하나라도 (N, N)”이 아니라 특정 한 칸만 도착을 확인한다.
-
프로그래머스 스쿨, “블록 이동하기” (https://school.programmers.co.kr/learn/courses/30/lessons/60063), 2026-09-30 조회. ↩