문제 보기 · Level 3 · 2023 KAKAO BLIND RECRUITMENT · 정답률 40% · 푼 사람 5,723명 (2026-09-30 기준)1

문제

n×m 격자에서 (x, y)에서 출발해 (r, c)로 탈출한다. 왼쪽 위가 (1, 1)이다. 한 번에 상하좌우로 한 칸씩 움직이고 격자 밖으로는 못 나간다. 정확히 k번 움직여 도착해야 하며, 같은 칸을 여러 번 지나도 된다. 이동을 d(아래), l(왼쪽), r(오른쪽), u(위)로 적은 문자열 중 사전 순으로 가장 앞선 것을 돌려준다. 불가능하면 "impossible"을 돌려준다.

  • 2 ≤ n, m ≤ 50
  • 1 ≤ k ≤ 2,500
  • 출발 칸과 탈출 칸은 다르다

풀이

막히면 한 단계씩 펼친다.

필요한 개념

그리디: 사전 순은 앞 글자부터 정해진다. 그래서 앞자리부터 가장 작은 글자를 고르되, 그 글자를 골라도 끝까지 갈 수 있는지만 확인한다.

1단계 · 작은 예로 손으로 풀기

2×2 격자, (1, 1) → (2, 2), k = 2

가능한 경로는 dr, rd 두 개다. 알파벳 순서는 d < l < r < u이므로 d로 시작하는 dr이 답이다.

3×3 격자, (1, 2) → (3, 3), k = 4라면 불가능하다. 가로 1칸, 세로 2칸이라 최소 3번은 움직여야 한다. 한 걸음 옆으로 갔다 돌아오면 2번이 늘어나니, 걸음 수는 3, 5, 7, …만 된다. 4는 안 된다.

2단계 · 가장 단순한 방법과 그 속도

길이 k인 문자열을 사전 순으로 모두 만들어 보며 처음 맞는 것을 고른다. 경우의 수가 4ᵏ이라, k = 2,500이면 1,500자리가 넘는 수다. 어림없다.

3단계 · 핵심 아이디어
  • 갈 수 있는지 판단: 지금 칸에서 탈출 칸까지 가로·세로 칸 수의 합(맨해튼 거리)을 dist, 남은 걸음을 remain이라 하자. dist ≤ remain이고 remain − dist가 짝수면 도착할 수 있다. 남는 걸음은 옆 칸에 갔다 돌아오기로 두 걸음씩 쓴다(격자가 2×2 이상이라 옆 칸은 늘 있다).
  • 홀수면 못 가는 까닭: 칸을 (행 + 열)이 짝수인 칸과 홀수인 칸, 두 색으로 칠하면 한 걸음마다 색이 바뀐다. 곧 격자는 이분 그래프다. 그래서 두 칸 사이를 어떤 길로 가든 걸음 수는 dist와 홀짝이 같고, remain − dist가 홀수면 도착할 수 없다.
  • 짝수 조건은 처음 한 번만: 한 걸음마다 dist는 1 늘거나 1 줄고 remain은 1 준다. 그래서 remain − dist의 홀짝은 끝까지 그대로다. 처음에 짝수면, 걸음마다 dist ≤ remain만 확인하면 된다.
  • 앞자리부터 가장 작은 글자: 걸음마다 d, l, r, u 순으로 보고, 격자 안이고 “그 칸에서 남은 걸음으로 도착할 수 있는” 첫 방향을 고른다. 사전 순은 앞 글자가 작으면 뒤와 상관없이 앞서므로, 이렇게 고른 글자를 되돌릴 일이 없다.
4단계 · 코드 흐름
  1. dist를 구한다. dist > k거나 k − dist가 홀수면 "impossible".
  2. k번 되풀이한다. 이번 걸음 뒤에 남는 걸음 remain = k − (지금까지 걸음) − 1.
  3. d, l, r, u 순으로 옮겨 본 칸이 격자 안이고 그 칸의 dist ≤ remain이면, 그리로 옮기고 글자를 붙인다.
  4. 모은 글자를 이어 돌려준다.
5단계 · 파이썬 코드 
MOVES = [("d", 1, 0), ("l", 0, -1), ("r", 0, 1), ("u", -1, 0)]   # 사전 순

def solution(n, m, x, y, r, c, k):
    dist = abs(x - r) + abs(y - c)
    if dist > k or (k - dist) % 2 == 1:
        return "impossible"
    path = []
    for step in range(k):
        remain = k - step - 1                # 이번 걸음 뒤에 남는 걸음 수
        for ch, dx, dy in MOVES:
            nx, ny = x + dx, y + dy
            if 1 <= nx <= n and 1 <= ny <= m and abs(nx - r) + abs(ny - c) <= remain:
                x, y = nx, ny
                path.append(ch)
                break                        # 가장 앞선 글자를 골랐으면 끝
    return "".join(path)
  • x는 행(위아래), y는 열(좌우)이다. d는 행 번호가 1 늘고, l은 열 번호가 1 준다.
  • abs(a): a의 절댓값이다.
  • break는 안쪽 for만 끝낸다. 바깥 for는 다음 걸음으로 넘어간다.
6단계 · 실행 추적

n = 3, m = 4, (2, 3) → (3, 1), k = 5. 처음 dist = 1 + 2 = 3이고 5 − 3 = 2는 짝수라 갈 수 있다.

걸음 뒤에 남는 걸음 해 본 방향 (옮긴 칸의 dist) 고른 글자 위치
1 4 d (2) d (3, 3)
2 3 d (밖), l (1) l (3, 2)
3 2 d (밖), l (0) l (3, 1)
4 1 d (밖), l (밖), r (1) r (3, 2)
5 0 d (밖), l (0) l (3, 1)

답은 dllrl이다. 4번째 걸음에서 이미 도착해 있지만 걸음이 남아, 가장 앞선 글자 중 되돌아올 수 있는 r로 한 칸 나갔다 온다.

7단계 · 복잡도와 흔한 실수

걸음마다 방향 4개를 보니 \(O(k)\), 많아야 1만 번이다.

  • 방향 순서를 d, l, r, u(알파벳 순)가 아닌 u, d, l, r(보통 쓰는 순)로 둔다.
  • 행·열을 거꾸로 써서 d를 열 방향으로 옮긴다.
  • 홀짝 조건을 빼먹어 도착하지 못하는 문자열을 돌려준다.
  • 깊이 우선 탐색을 가지치기 없이 돌려 시간 초과가 난다. “dist > remain이면 그 가지를 버린다”는 가지치기를 넣으면, 사전 순으로 도는 탐색이 처음 찾는 경로가 답이고 되돌아갈 일도 없어 이 풀이와 같아진다.
검증: 문제의 예시 3개를 통과했고, 무작위 입력 1,500개(격자 4×4 이하, k ≤ 7)에서 “길이 k 문자열을 사전 순으로 모두 만들어 처음 맞는 것을 고르는” 풀이와 결과가 같았다. 6단계 표의 각 줄과 가장 큰 입력(k = 2,500)도 확인했다 — 22_pg150365_p1.py

  1. 프로그래머스 스쿨, “미로 탈출 명령어” (https://school.programmers.co.kr/learn/courses/30/lessons/150365), 2026-09-30 조회. ↩