[코딩 테스트, 더 이상 미룰 수 없다] 프로그래머스 lv1 키패드 누르기 - B/DFS와 좌표 계산 분리해서 유형좁히기

 

 

나는 보통 문제에 좌표가 언급된다면 BFS나 구현을 우선적으로 떠올린다.

 

---

처음 떠올린 풀이

처음에는

BFS

↓

거리 계산

↓

더 가까운 손 선택

이라고 생각했다.

하지만 BFS가 필요한 조건이 하나도 없었다.

---

BFS는 언제 사용할까?

BFS는 보통

• 미로
• 그래프
• 최단 거리
• 장애물이 있는 이동

처럼 탐색을 통해 길을 찾아야 하는 문제에서 사용한다.

예를 들어

출발

↓

이동 가능한 칸 탐색

↓

최단 거리 계산

이런 구조라면 BFS를 떠올리는 것이 맞다.

---

그런데 키패드는?

키패드는 이미 위치가 모두 정해져 있다.

1 2 3

4 5 6

7 8 9

* 0 #

즉,

• 길을 찾을 필요도 없고
• 장애물도 없으며
• 탐색도 필요 없다.

필요한 것은 각 숫자의 좌표뿐이었다.

---

좌표로 바꾸기

그래서 먼저 각 숫자의 좌표를 Dictionary로 저장했다.

position = {
    1:(0,0), 2:(0,1), 3:(0,2),
    4:(1,0), 5:(1,1), 6:(1,2),
    7:(2,0), 8:(2,1), 9:(2,2),
    "*":(3,0), 0:(3,1), "#":(3,2)
}

이렇게 하면 숫자를 누를 때마다 좌표를 바로 가져올 수 있다.

---

상태(State)만 관리하면 된다.

이 문제에서 계속 변하는 것은 두 가지뿐이다.

왼손 위치

오른손 위치

즉,

left = "*"
right = "#"

만 계속 업데이트하면 된다.

버튼을 누르면

left = n

또는

right = n

으로 현재 위치만 변경하면 된다.

---

거리 계산도 탐색이 아니다.

중앙 버튼(2, 5, 8, 0)은

왼손과 오른손의 거리를 비교해야 한다.

이때 사용하는 것이 맨해튼 거리(Manhattan Distance) 이다.

left_dist = abs(r1-r3) + abs(c1-c3)
right_dist = abs(r2-r3) + abs(c2-c3)

BFS로 이동 경로를 찾는 것이 아니라

좌표만 이용해서 거리를 계산하면 끝난다.

---

이번 문제를 통해 얻은 사고 과정

처음에는

이동

↓

BFS?

라고 생각했다.

하지만 문제를 다시 분석하면서

좌표가 고정되어 있다.

↓

탐색이 필요 없다.

↓

좌표 계산

↓

맨해튼 거리

로 사고를 수정할 수 있었다.

이 과정이 이번 문제에서 가장 큰 수확이었다.

---

앞으로 비슷한 문제를 만나면

문제를 읽고 가장 먼저 아래 질문을 해보려고 한다.

① 정말 탐색이 필요한가?

② 좌표가 이미 정해져 있는가?

③ 현재 상태만 관리하면 되는 문제인가?

이 세 가지 질문을 먼저 하면

BFS를 사용할 문제인지,

아니면 단순한 좌표 계산 문제인지를 빠르게 구분할 수 있을 것 같다.

---

이번 문제 복습 포인트

• 이동이 있다고 해서 무조건 BFS를 사용하는 것은 아니다.
• 좌표가 고정되어 있다면 탐색보다 좌표 계산을 먼저 생각한다.
• 좌표는 Dictionary로 저장하면 빠르게 조회할 수 있다.
• 현재 변하는 값은 왼손 위치와 오른손 위치(State) 뿐이다.
• 거리 계산은 맨해튼 거리를 사용하자.(외워서 툭 치면 나올정도)