알고리즘 문제를 풀다 보면 문제 분류를 파악하고 머릿속의 템플릿을 꺼내어 문제에 맞추려는 경향이 있다. 이번 22년도 카카오 기출 '양과 늑대' 문제를 풀며, 이런 접근 방식이 어떻게 한계를 보이고 이를 어떻게 극복해야 하는지 사고의 흐름과 코드 변천 과정을 통해 정리해 보았다.
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92343
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
1. 초기 접근: 경로 탐색 프레임에 갇힌 사고
처음 문제를 접했을 때의 생각 흐름은 다음과 같았다.
- 2 <= 노드(info) <= 17. 노드 수를 N이라 할 때 N은 약 10.
- 엣지도 2N -> N.
- 스테이트 스페이스 = 현재 방문한 노드, 양의 수, 늑대의 수.
- transition = 발견한 노드 중 방문하지 않은 곳.
- DFS/BFS 완전 탐색을 했을 때 O(N)이 매우 작으므로 그리디가 아닌 완전탐색 문제다.
- 결과는 양의 최대 수를 반환하는 것이다 -> 그에 따라서 스테이트 압축을 할 수 있다.
- 스테이트 = 양/늑대 수, 트랜지션 = 양을 고르거나 늑대를 고른다.
- 조건에 맞지 않는 분기는 더 이상 탐색하지 않는다. (DFS 가지치기)
- 양의 최대 수를 갱신하고 있다가 모든 경우의 수 탐색이 끝나면 종료한다. (백트래킹 + 최적해 갱신)
루트 노드부터 DFS로 탐색하되, 재귀 호출마다 별도의 visited 배열을 복사해서 넘기면 모든 경우의 수가 유지될 것이라고 생각했다.
visited 배열 복제로 모든 경우를 탐색할 수 있다는 착각
왜 visited 복사만으로는 부족했을까? 일반적인 DFS는 한 방향으로 쭉 내려갔다가 막히면 return해서 부모 노드로 돌아온다. 하지만 이 문제는 "왼쪽 끝까지 갔다가, 갑자기 오른쪽 중간에 있는 노드로 순간이동" 하는 식의 움직임이 필요하다.
현재 코드의 한계는 명확했다. 0번 -> 1번 -> 8번 순서로 탐색하려고 할 때, 8번이 0번의 자식이라면 1번의 재귀 함수 안에서는 8번으로 갈 방법이 없다. 1번의 adjacent[1]에는 8번이 없기 때문이다.
재귀의 특성상 1번 노드에서 DFS가 끝나고 0번으로 돌아와야만 비로소 8번으로 갈 수 있는데, 이때는 이미 1번에서 얻은 양의 수(lamb) 상태가 초기화되어 버린다.
def solution(info, edges):
answer = 0
N = len(info)
adjacent = [[] for _ in range(N)]
for s,e in edges:
adjacent[s].append(e)
# 백트래킹 = DFS + 늑대가 양 이상이 될때 가지치기 + 최적해 갱신으로 구현
def dfs(node, visited, lamb, wolf):
nonlocal answer
visited[node] = True
if info[node] == 0:
lamb += 1
if info[node] == 1:
wolf += 1
if lamb <= wolf: # pruning 반복문 안쪽말고 여기에 가지치기 해봄. 어차피 똑같겠지?
return
if answer <= lamb: # 최적해 갱신
answer = lamb
for nxt in adjacent[node]:
if not visited[nxt]:
dfs(nxt, visited[:], lamb, wolf)
dfs(0, [False] * (N), 0, 0)
return answer2. 과도기와 리팩토링: 진짜 상태(State)의 발견
급 리팩토링 - 통과
코딩 테스트 환경에서는 시간도 소중하기에, 매번 모든 adjacent를 뒤지는 식으로 이중 반복문을 적용해 보았다.
def solution(info, edges):
answer = 0
N = len(info)
adjacent = [[] for _ in range(N)]
for s,e in edges:
adjacent[s].append(e)
def dfs(node, visited, lamb, wolf):
nonlocal answer
visited[node] = True
if info[node] == 0:
lamb += 1
if info[node] == 1:
wolf += 1
if lamb <= wolf:
return
if answer <= lamb:
answer = lamb
for i in range(N):
if visited[i]:
for nxt in adjacent[i]:
if not visited[nxt]:
dfs(nxt, visited[:], lamb, wolf)
dfs(0, [False] * (N), 0, 0)
return answer정답은 통과했지만, 매번 전체 맵을 스캔하는 이중 반복문은 구조적으로 비효율적이었다.
node를 빼고 visited 대신 possible 도입
코드를 다시 보며 애초에 node 파라미터 자체가 의미가 없다는 것을 깨달았다. DFS에서 노드를 파라미터로 넘겨주는 이유는 해당 node에서 다음으로 넘어가라는 의미인데, 이 문제는 특정 node에서 출발하는 것이 아니라 '지금까지 간 곳 전체'에서 다음 갈 곳을 정하는 것이기 때문이다.
즉, 갈 수 있는 곳을 유지하는 것 자체가 진짜 스테이트 스페이스였다.
def solution(info, edges):
answer = 0
N = len(info)
adj = [[] for _ in range(N)]
for s,e in edges:
adj[s].append(e)
def dfs(possible, lamb, wolf):
nonlocal answer
if answer <= lamb: # 최적해 갱신
answer = lamb
for i in range(len(possible)):
nxt = possible[i] # i는 possible 인덱스, nxt 실제 번호
# 트리 자료구조이기에 사이클이 없으므로 adj에는 기존에 넣은 possible이랑 안 겹칠 것이다.
new_possible = possible[:i] + possible[i+1:] + adj[nxt]
new_lamb = lamb
new_wolf = wolf
if info[nxt] == 0:
new_lamb += 1
if info[nxt] == 1:
new_wolf += 1
if new_lamb > new_wolf:
dfs(new_possible, new_lamb, new_wolf)
lamb, wolf = 0, 0
if info[0] == 0:
lamb = 1
if info[0] == 1:
wolf = 1
dfs(adj[0], lamb, wolf)
return answer3. 깨달음: 알고리즘 템플릿의 미끼를 피하는 법
코드를 완성하고 나서 한 가지 의문이 남았다. '이런 형태의 스테이트(possible)를 처음부터 직관적으로 떠올려 내는 건 어려운데, 어떻게 접근해야 바로 떠올릴 수 있을까?'
여기서 내 접근 방식 자체를 되돌아보며 패러다임이 전환되는 깨달음을 얻었다.
기존의 잘못된 사고 흐름:
알고리즘 분류 파악(완전탐색) -> 템플릿 꺼내기(표준 DFS) -> 문제에 억지로 끼워 맞추기 -> 안 맞아서 수정
이렇게 접근하면 최적의 스테이트 스페이스를 절대 도출하지 못한다.
로직은 억지스러워지고 시간 측면에서 비효율이 발생하며, 정답을 피해갈 수도 있다.
사실 예시를 봤을 때 가장 먼저 생각나는 직관적인 스테이트(노드와 방문 배열)는 출제자가 심어놓은 미끼에 가깝다.
어려운 문제에서는 이 미끼가 무조건 모순과 비효율을 낳는다.
올바른 사고 흐름:
요구사항 분석 -> "행동(Action)" 정의 -> 행동에 필요한 "상태(State)" 도출 -> 알고리즘 적용
이 흐름에 맞춰 문제를 다시 뜯어보았다.
- 이 게임에서 내 턴마다 할 수 있는 행동이 뭐지?(Action) -> 발견한 노드 중 안 간 곳 하나 고르기.
- 그럼 내 턴마다 나한테 주어져야 하는 정보(상태)는 뭐지? -> 양의 수, 늑대의 수, 그리고 지금 당장 고를 수 있는 후보지 목록. (Action을 정의하니 정답 지향적인 새로운 관점이 도출된다)
- 현재 내 위치(node)가 다음 행동에 영향을 주나? -> 안 주면 상태(파라미터)에서 과감히 뺀다.
이 1, 2, 3번 과정을 마치면 탐색 단위 함수의 파라미터, 즉 '스테이트'가 완성된다.
DFS라면 함수의 파라미터가 되고, BFS라면 큐에 삽입하는 튜플의 내용이 된다.
이 상태만 정확히 정의해 내면 사실상 문제는 다 푼 것이나 다름없다.
4. 내 깨달음은 사실 FSM(유한 상태 머신)의 재발명이었다
앞선 과정들을 거치며 얻은 통찰은, 사실 소프트웨어 공학 시간에 배웠던 유한 상태 머신(FSM, Finite State Machine) 개념을 코딩 테스트 환경에서 다시 발명해 낸 것에 불과했다.
FSM을 코딩 테스트의 탐색(DFS/BFS)과 동적 계획법(DP)에 적용하는 것은 알고리즘 문제를 대하는 패러다임 자체를 뒤집는 매우 강력한 무기다. 이 관점을 장착하면 왜 아까와 같은 "물리적 경로 탐색"의 함정에 빠지지 않게 되는지, CS 지식과 코딩 테스트 실전 압축 지식을 엮어서 정리해 보았다.
CS적 관점: 상태 머신(State Machine)의 본질
소프트웨어 공학에서 상태 머신은 시스템의 동작을 모델링하는 도구다. 자판기를 예로 들면, 자판기는 특정 '상태(State)'에 머물러 있다가 동전을 넣거나 버튼을 누르는 '이벤트/행동(Action)'가 발생하면 다른 상태로 '전이(Transition)'한다.
이를 수학적으로 정의하면 다음 요소들로 이루어진다.
- S: 가능한 모든 상태의 집합 (State Space)
- S_0: 초기 상태 (Initial State)
- A: 가능한 행동/이벤트의 집합 (Actions)
- T(s, a) -> s': 상태 s에서 행동 a를 취했을 때 새로운 상태 s'로 넘어가는 전이 함수(Transition Function)
여기서 가장 중요한 핵심은 "시스템은 한순간에 오직 하나의 상태만 가진다"는 것과, "과거에 어떤 경로를 거쳐왔든, 현재의 상태가 같다면 미래의 가능성도 완벽히 똑같다(Markov Property)"는 점이다.
코테 관점: 물리적 공간(Physical Space)에서 상태 공간(State Space)으로
알고리즘을 처음 공부할 때, 많은 사람들이 DFS/BFS를 '미로 찾기'나 '트리 순회'로 시작한다. 그러다 보니 뇌가 자연스럽게 "물리적인 위치(x, y 좌표나 노드 번호)"를 중심으로 굳어져 버린다.
하지만 문제의 난이도가 올라갈수록 주어지는 환경은 단순한 2D 배열이나 트리가 아니라, 보이지 않는 '상태 공간(State Space)'을 탐색하도록 요구한다.
물리적 관점 (초기 접근 방식의 한계)
- 인식: "나는 지금 1번 노드에 서 있다. 여기서 이어진 간선(Edge)을 타고 다음 노드로 걸어간다."
- 한계: '양과 늑대'처럼 순간이동을 하거나, 특정 아이템을 먹어서 맵의 성질 자체가 바뀌는 문제에서는 물리적 지도만으로는 탐색이 불가능해진다.
상태 머신 관점 (리팩토링 성공 방식)
- 인식: "이 프로그램은 현재 특정 스냅샷(Snapshot)을 가지고 있다. 내가 여기서 취할 수 있는 행동은 주어진 선택지 목록 중 하나를 고르는 것이다."
이 관점을 '양과 늑대' 문제에 적용하면 다음과 같이 모델링된다.
- 상태(s): {현재 양의 수, 현재 늑대의 수, 다음에 갈 수 있는 문(노드)들의 목록}
- 행동(a): "목록 중 하나(예: 노드 8)의 문을 연다."
- 전이(T): 양/늑대 수가 갱신되고, 내가 연 문의 자식 노드들이 목록에 추가된 새로운 상태(s')가 파생된다.
이처럼 문제를 상태 머신으로 바라보면, 출제자가 던져준 물리적인 노드의 연결(Tree)은 단지 다음 상태를 계산하기 위한 '규칙서(Rulebook)'로 전락하게 된다. 내 현재 위치(node)는 더 이상 상태를 정의하는 데 필요가 없어지는 것이다.
5. 상태 머신 관점이 뇌를 어떻게 개조하는가?
이 사고방식을 체화하면 코딩 테스트의 여러 고난도 유형에서 비약적인 성장이 일어난다.
다차원(Multi-dimensional) 탐색의 두려움 소멸
"열쇠를 먹어야만 열리는 문이 있는 미로 찾기" 같은 문제를 만났을 때, 물리적 공간에 갇힌 뇌는 "어떡하지? 방문했던 곳을 또 가야 하는데 방문 처리를 어떻게 지우지?"라며 패닉에 빠진다.
하지만 상태 머신을 이해한 뇌는 침착하게 상태를 재정의한다.
- 기존 상태: (x, y)
- 새로운 상태: (x, y, 열쇠 보유 여부)
- 열쇠가 없을 때의 (2, 2)와 열쇠가 있을 때의 (2, 2)는 아예 다른 우주(상태)로 취급된다. 이제 3차원 상태 공간에서 똑같이 BFS를 돌리면 그만이다.
동적 계획법(DP)과의 완벽한 통합
DP는 결국 "상태 머신에서 이미 계산된 상태의 결과값을 캐싱(Memoization)하는 것"에 불과하다. DP[state] = 최적해라고 할 때, 상태를 완벽하게 정의해 냈다면 기존의 완전 탐색(DFS) 코드 상단에 단 3줄의 메모이제이션 코드만 추가하면 그게 바로 DP가 된다. 탐색과 DP의 경계가 무너지는 순간이다.
상태 압축(Bitmasking)의 당위성 이해
상태 머신 관점에서는 파라미터(상태)가 길어지고 복잡해질수록 메모리를 많이 쓰고 연산이 느려진다.
'양과 늑대' 문제에서 배열 형태의 possible 리스트는 상태를 잘 표현했지만, 매번 배열을 쪼개고 합치면 오버헤드가 발생한다.
"이 리스트 상태를 어떻게 하면 가장 가볍게 만들까?"를 고민하다가, "전체 노드가 17개뿐이니 0과 1로 켜고 끄는 17자리 이진수(정수 1개)로 상태를 나타내자!"라는 결론에 도달하게 된다. 이것이 바로 비트마스킹의 본질이자 도입 이유다.
코드는 조금만 수정하면 비트마스킹 전환을 할 수 있다.
def solution(info, edges):
answer = 0
N = len(info)
adj = [[] for _ in range(N)]
for s,e in edges:
adj[s].append(e)
def dfs(possible, lamb, wolf):
nonlocal answer
if answer<=lamb: # 최적해 갱신
answer = lamb
for i in range(N):
# nxt = possible[i] # i는 possible 인덱스, nxt 실제 번호
# 이제는 i가 진짜 번호이자 인덱스가 됨
if 1<<i & possible == 0:
continue
# new_possible = possible[:i] + possible[i+1:] + adj[nxt] -> 다음을 삭제 다음인접을 추가
# 이 방식으로 대체. 물론 new_possible 복제하면서 해야되는건 같음
new_possible = possible
new_possible &= ~(1<<i)
for j in adj[i]:
new_possible |= 1<<j
new_lamb = lamb
new_wolf = wolf
if info[i] == 0:
new_lamb += 1
if info[i] == 1:
new_wolf += 1
if new_lamb > new_wolf:
dfs(new_possible, new_lamb, new_wolf)
lamb,wolf = 0,0
possible = 0
if info[0] == 0:
lamb = 1
if info[0] == 1:
wolf = 1
for i in adj[0]:
possible |= 1<<i
dfs(possible, lamb, wolf)
return answer
6. 요약
앞으로 복잡한 탐색 문제를 만날 때마다, 코드부터 짜지 말고 주석으로 다음 세 가지를 반드시 정의하는 습관을 들여보자.
- State (상태): 현재 상황을 완벽히 복원하기 위해 필요한 최소한의 데이터는 무엇인가? (물리적 위치인가? 아이템인가? 남은 시간인가?)
- Action (행동): 이 상태에서 내가 할 수 있는 유효한 선택은 무엇인가?
- Transition (전이): 그 행동을 했을 때, State의 데이터들은 각각 어떻게 변하는가?
이 틀에 맞춰서 사고를 강제하면, 템플릿의 미끼에 낚일 일도 없고 아무리 복잡한 문제라도 결국 기계적인 상태 변환 코드로 환원될 것이다.
댓글