BOJ 풀이 노트: 완전탐색 순회와 공기청정기 시뮬레이션 점검

2026. 2. 27. · tech

BOJ 10971과 17144를 대상으로, 상태 가지치기 기반 완전탐색과 단계별 시뮬레이션 구현 포인트를 실전 기준으로 정리한 풀이 노트.

오늘은 성격이 다른 두 문제를 묶어서 풀었다.

• BOJ 10971 - 외판원 순회 2
• BOJ 17144 - 미세먼지 안녕!

10971은 “모든 도시를 한 번씩 방문하고 시작점으로 돌아오는 최소 비용”을 찾는 완전탐색 계열이고, 17144는 “확산 + 공기청정기 순환”을 시간 단위로 정확히 구현하는 시뮬레이션 계열이다. 둘 다 정답 아이디어보다 구현 디테일에서 점수가 갈린다.

1) BOJ 10971 - 외판원 순회 2

문제 핵심 요약

도시 간 이동 비용이 주어질 때, 한 도시에서 출발해 모든 도시를 정확히 한 번씩 방문하고 다시 출발 도시로 돌아오는 순회의 최소 비용을 구하는 문제다. 경로가 없는 경우(비용 0)는 이동 불가로 처리해야 한다.

접근 아이디어(왜 이 방법인지)

도시 수가 크지 않아서(완전탐색 가능 범위) 백트래킹으로 모든 순회를 확인할 수 있다.

핵심은 두 가지다.

1. visited로 중복 방문을 막는다.
2. 현재 누적 비용이 이미 최적값 이상이면 바로 가지치기한다.

시작 도시를 고정해도 되지만, 구현을 단순화하려고 모든 시작점을 한 번씩 돌리되 같은 DFS 로직을 재사용했다.

시간/공간 복잡도

• 시간: 최악 O(N!) (가지치기로 실제 수행은 감소)
• 공간: O(N) (방문 배열 + 재귀 스택)

실수하기 쉬운 포인트

• W[a][b] == 0을 비용 0으로 오해하면 안 되고, “이동 불가”로 처리해야 한다.
• 모든 도시를 방문한 뒤 마지막 복귀 간선(cur -> start)이 없을 수 있다. 이 경우는 정답 후보로 쓰면 안 된다.
• 가지치기 조건을 빼면 시간 초과 위험이 커진다.

C++ 코드 설명(핵심 라인)

if (cost >= answer) return;

현재 경로가 이미 최적 해보다 나쁘면 즉시 중단해 탐색량을 줄인다.

if (depth == N) {
    if (W[cur][start] != 0) {
        answer = min(answer, cost + W[cur][start]);
    }
    return;
}

모든 도시를 방문한 시점에서 시작점 복귀 가능 여부를 확인하고 정답을 갱신한다.

다른 풀이 가능성

• 비트마스크 DP(TSP DP)로도 풀 수 있다. 이 방식은 상태 정의가 명확하고 중복 계산을 더 줄일 수 있다.
• 다만 이 문제 크기에서는 백트래킹 + 가지치기만으로도 충분히 통과 가능하다.

2) BOJ 17144 - 미세먼지 안녕!

문제 핵심 요약

매 초마다 방 안의 미세먼지가 인접 칸으로 확산되고, 공기청정기가 바람 순환으로 먼지를 제거한다. T초 뒤 남은 미세먼지 총량을 구하는 구현 문제다.

접근 아이디어(왜 이 방법인지)

문제를 “확산 단계”와 “공기청정기 작동 단계”로 분리하면 안정적으로 구현할 수 있다.

• 확산: 현재 격자를 기준으로 동시에 퍼져야 하므로 add 보조 배열에 누적한 뒤 한 번에 반영
• 청정기: 위쪽 반시계, 아래쪽 시계 방향으로 테두리 값을 한 칸씩 당겨서 순환 구현

시뮬레이션 문제는 상태 갱신 순서가 정답과 직결되므로 단계 분리가 가장 안전하다.

시간/공간 복잡도

• 시간: O(T * R * C)
• 공간: O(R * C) (보조 확산 배열)

실수하기 쉬운 포인트

• 확산을 제자리에서 바로 반영하면 동시성이 깨져 오답이 된다.
• 공기청정기 칸(-1)으로는 확산되면 안 된다.
• 순환 이동 순서를 잘못 잡으면 이전 값이 덮여서 값이 꼬인다.
• 청정기 바로 오른쪽 칸은 매 단계 0으로 강제해야 한다.

C++ 코드 설명(핵심 라인)

int amount = room[i][j] / 5;
...
add[ni][nj] += amount;
room[i][j] -= amount * cnt;

확산량을 계산해 주변에 누적하고, 원래 칸에서는 확산된 총량만큼 차감한다.

room[upCleaner][1] = 0;
room[downCleaner][1] = 0;

공기청정기에서 나온 바람으로 유입되는 위치는 항상 깨끗한 공기이므로 0으로 리셋한다.

다른 풀이 가능성

• 방향 벡터/경로 리스트를 미리 만들어 순환 경로를 일반화할 수 있다.
• 하지만 이 문제는 상/하 청정기 규칙이 고정이라, 구간별 for문으로 직접 구현하는 방식이 디버깅에 더 유리하다.

오늘 정리 포인트는 명확하다.

• 10971은 “불가능 간선 처리 + 가지치기”가 핵심이다.
• 17144는 “동시 확산 분리 + 순환 순서 고정”이 핵심이다.

완전탐색과 시뮬레이션 기본기를 같이 점검하기 좋은 조합이었다.