[코드트리] DFS/BFS 알고리즘 약점 극복 학습 후기 - 유형별 커리큘럼으로 감각 잡기
#코드트리 #코딩테스트 #코테공부 #DFS #BFS #알고리즘기초
코드트리 3주차 후기. 이번 주는 DFS/BFS를 집중적으로 팠다.
솔직히 말하면 DFS/BFS는 “알긴 알아” 상태였다. 개념 설명 들으면 이해는 가는데, 막상 새 문제 앞에 앉으면 손이 안 움직이는 그 상태. 이번 주에 그걸 좀 뚫었다.
I. 코드트리의 커리큘럼 구조 — 쎈 수학처럼 유형을 드릴한다
코드트리를 쓰면서 느낀 건, 구조 자체가 굉장히 잘 짜여 있다는 것이다.
보통 알고리즘 공부를 혼자 하면 이런 식으로 흘러간다.
유튜브 강의 봄 → “이해했다!” → 백준 가서 비슷한 문제 풀어보려고 탐색 → 뭘 풀어야 할지 모름 → 아무 문제나 잡음 → 너무 어렵거나 너무 쉬움 → 흥미 잃음
코드트리는 이 흐름을 레슨 단위로 끊어줬다.
개념 설명
↓
기본 문제 (개념을 그대로 적용하면 풀리는 것들)
↓
연습 문제 (조건이 하나씩 붙기 시작함)
↓
테스트 문제 (실전 수준)
이게 마치 수학 교재 쎈을 푸는 느낌이다. 개념 → 유형 A → 유형 B → 실전 순서로 점진적으로 올라가는 것. 백준처럼 내가 직접 레벨을 판단해서 문제를 골라야 하는 게 아니라, 코드트리가 이 순서를 다 잡아준다.
특히 DFS/BFS 단원이 그랬다. 처음에는 단순히 “방문 여부 체크하고 4방향 탐색” 수준이었는데, 기본 → 연습 → 테스트를 따라가면서 자연스럽게 아래 패턴이 머리에 박혔다.
II. DFS vs BFS — “언제 뭘 쓰는지”가 핵심이다
공부하면서 정리한 판단 기준:
| 문제 발문 패턴 | 선택 |
|---|---|
| 연결된 칸 / 그룹 / 영역 찾기 | DFS 또는 BFS |
| 최소 몇 번 / 최단 거리 | BFS 우선 |
| 모든 경우를 다 따져야 함 | DFS (백트래킹) |
| 동시에 확산되는 상황 | BFS |
처음엔 이걸 외우려고 했는데, 기본 문제들을 쭉 풀고 나니 이게 외우는 게 아니라 느끼는 거더라. 최단 거리를 BFS로 구하는 이유는 BFS가 레이어(거리) 단위로 탐색하기 때문이고, DFS는 그걸 보장해주지 않기 때문. 이걸 직접 틀려보고 나서야 제대로 이해했다.
BFS 기본 구조
queue<pair<int,int>> q;
q.push({sx, sy});
visited[sx][sy] = true;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (visited[nx][ny]) continue;
if (board[nx][ny] == 막히는값) continue;
visited[nx][ny] = true;
q.push({nx, ny});
}
}
BFS의 핵심은 Queue가 FIFO라는 것. 먼저 넣은 게 먼저 나오니까, 거리가 짧은 것부터 순서대로 처리된다. 그래서 처음 도달했을 때의 거리가 최단 거리가 된다.
auto [x, y] = q.front(); q.pop(); 이 두 줄도 처음엔 낯설었는데, C++17 구조 바인딩 문법으로 pair를 자동으로 쪼개주는 것. q.front()로 읽기 → q.pop()으로 삭제 이걸 항상 같이 써야 한다.
DFS 기본 구조
void dfs(int x, int y) {
visited[x][y] = true;
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (visited[nx][ny]) continue;
if (board[nx][ny] == 막히는값) continue;
dfs(nx, ny);
}
}
재귀로 깊이 우선 탐색. “최단거리를 보장하지 않아도 되는 경우” — 영역 개수 세기, 연결 여부 확인 같은 문제에서 주로 쓴다.
방향 배열 — 매번 쓰는 템플릿
const int dx[] = { 0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};
이게 없으면 4방향 조건문을 네 번 써야 한다. 이걸 배열로 정의해두면 for (int d = 0; d < 4; d++) 루프 하나로 끝난다. 처음에 dx, dy 이름 때문에 수학 좌표계랑 헷갈렸는데 그냥 행 방향 / 열 방향이라고 생각하면 된다.
범위 체크도 매번 쓰는 거니까 함수로 만들어두는 게 낫다:
inline bool inRange(int r, int c) {
return 0 <= r && r < N && 0 <= c && c < N;
}
III. 레슨 단위 학습이 바꾼 풀이 감각
기본 문제를 풀 때는 거의 템플릿 그대로 쓰면 된다. 그런데 연습 문제부터 조건이 붙기 시작한다.
- “두 종류의 장애물이 있고, 한 종류는 통과 가능”
- “이동 거리가 짧은 것 중 행 번호, 열 번호 순으로 우선순위”
- “여러 칸에서 동시에 BFS 시작”
이때 기본 BFS 구조에서 continue 조건을 하나씩 추가하면 된다는 걸 연습 문제들을 풀면서 자연스럽게 익혔다. 문제마다 제약 조건이 다른데, “어떤 조건을 어느 위치에 넣어야 하는가”를 반복하다 보니 감각이 생겼다.
삼성 SW 기출 문제인 AI 로봇청소기를 풀면서 이게 확 느껴졌다. BFS를 써야 한다는 건 금방 알겠는데, 조건이 많았다:
- 이동 거리가 가장 가까운 오염 칸으로 이동
- 물건이 있는 칸, 다른 로봇이 있는 칸은 지나갈 수 없음
- 거리가 같으면 행 번호 → 열 번호 우선순위
예전이었으면 “조건이 많아서 복잡하다”고 느꼈을 텐데, 연습 문제들을 통해 각 조건을 if (...) continue; 형태로 쌓아가는 패턴이 이미 손에 익어 있어서 훨씬 수월했다.
if (!inRange(nr, nc)) continue; // 범위 체크
if (dist[nr][nc] != -1) continue; // 이미 방문
if (A[nr][nc] < 0) continue; // 물건 있는 칸
if (B[nr][nc] != -1) continue; // 다른 로봇 점유
이런 식으로 제약 조건을 위에서부터 쌓아 내려오면 된다. 기본 문제에서는 2개였던 continue가 연습/테스트로 가면서 4~5개가 되는 것뿐이다.
IV. 코드트리 해설/토론이 도움된 부분
코드트리의 모범 코드를 보면서 내 코드와 비교하는 게 생각보다 도움이 됐다.
내가 풀고 나서 모범 코드를 보면 항상 두 가지 중 하나다:
- 내 코드와 거의 같음 → 이번엔 제대로 이해했구나
- 훨씬 깔끔함 → 이 패턴을 몰랐구나
특히 bestCell = min(bestCell, make_pair(nr, nc)) 처럼 pair의 비교 연산자를 이용해서 행 번호 → 열 번호 우선순위를 자동으로 처리하는 부분은 모범 코드에서 처음 봤다. pair는 기본적으로 first를 먼저 비교하고 같으면 second를 비교하기 때문에, 따로 조건문 안 써도 된다는 걸 그때 알았다.
V. 타 서비스 비교 — 코드트리 vs 백준 vs 프로그래머스
| 코드트리 | 백준 | 프로그래머스 | |
|---|---|---|---|
| 커리큘럼 | 유형별 체계적 | 없음 (자기가 고름) | 레벨별 있음 |
| 해설 | 자세한 모범 코드 제공 | 없음 (블로그 의존) | 일부 제공 |
| 약점 파악 | 갭체크로 자동 진단 | 직접 파악해야 함 | 없음 |
| 적합한 시기 | 기초 다질 때 / 유형별 드릴 | 대량 풀이 연습 | 카카오/네이버 준비 |
백준은 문제 수가 워낙 많아서 막히면 찾을 수 있는 자료도 많다는 게 장점인데, 뭘 풀어야 할지 방향을 못 잡으면 시간 낭비가 심하다. 코드트리는 그 방향을 잡아주는 역할을 해준다고 느꼈다.
프로그래머스는 카카오, 네이버 스타일 문제를 준비할 때는 좋은데, DFS/BFS처럼 유형을 집중적으로 파고들기는 구조가 아니다.
결국 지금 내 상황처럼 “기본기를 체계적으로 쌓고 싶은” 시기에는 코드트리가 맞는 것 같다. 갭체크로 약점 유형 진단 → 레슨 단위 기본/연습/테스트 드릴 → 모범 코드로 패턴 확인하는 흐름이 지금 내 수준에 잘 맞는다.
다음 주는 BFS 심화(다중 출발점, 레이어 단위 처리)랑 백트래킹 쪽을 볼 것 같다. 이번 주처럼 “아는 것 같았는데 실제로는 몰랐던” 부분이 또 나올 거라고 생각하니 기대 반 긴장 반.