[코딩테스트 준비] 실버 2문제 (1260 DFS와 BFS, 1303 전투)

1260 DFS와 BFS

 

이 문제는 그래프를 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 방식으로 탐색한 결과를 출력하는 문제다.
탐색 과정에서 방문 가능한 정점이 여러 개일 경우 정점 번호가 작은 것부터 방문해야 한다는 조건이 핵심이다.

 

문제 핵심 조건

• 정점 번호: 1 ~ N
• 간선은 양방향
• 같은 두 정점 사이에 여러 간선 가능
• DFS 결과를 먼저 출력, 다음 줄에 BFS 결과 출력
• 시작 정점 V부터 탐색

 

풀이 전략

1. 인접 리스트 사용

정점 수와 간선 수를 고려했을 때 인접 행렬보다 인접 리스트가 메모리와 시간 면에서 효율적이다.

2. 오름차순 방문을 위한 정렬

DFS와 BFS 모두에서 작은 번호의 정점을 먼저 방문해야 하므로
각 정점의 인접 리스트를 미리 오름차순으로 정렬한다.

3. DFS와 BFS 방문 배열 분리

DFS 탐색이 끝난 뒤 BFS를 수행해야 하므로, 방문 여부 배열을 각각 따로 관리한다.

 

DFS 탐색 설명

DFS는 한 정점에서 시작해 갈 수 있는 경로를 끝까지 탐색한 뒤,
더 이상 진행할 수 없으면 이전 정점으로 돌아가 다른 경로를 탐색한다.
재귀 호출을 사용하면 구현이 간단하다.

예제 입력에서 DFS 방문 순서는 다음과 같다.

1 → 2 → 4 → 3

 

BFS 탐색 설명

BFS는 시작 정점에서 가까운 정점부터 순서대로 탐색한다.
큐를 사용해 현재 정점과 연결된 모든 정점을 먼저 방문한 후 다음 단계로 넘어간다.

예제 입력에서 BFS 방문 순서는 다음과 같다.

1 → 2 → 3 → 4

 

시간 복잡도

• 그래프 구성 및 정렬: O(N + M log M)
• DFS 탐색: O(N + M)
• BFS 탐색: O(N + M)

입력 제한 내에서 충분히 통과 가능한 구조다.

 

 

 

1303 전투

풀이 전략

 

1. 격자 그래프 탐색 문제

이 문제는 2차원 격자에서 연결 요소(Connected Component) 를 찾는 문제다.
DFS 또는 BFS를 사용해 같은 색으로 연결된 영역의 크기를 구하면 된다.

2. 방문 배열 사용

이미 계산한 병사를 다시 세지 않도록 방문 여부를 체크한다.

3. 그룹 단위로 위력 계산

• DFS/BFS로 하나의 그룹을 탐색하면서 병사 수를 센다.
• 탐색이 끝나면 해당 그룹의 크기를 제곱해 진영별 합에 더한다.

DFS 탐색 동작 설명

• 아직 방문하지 않은 병사를 만나면 DFS 시작
• 상하좌우로 같은 색의 병사를 재귀적으로 탐색
• 하나의 DFS 호출이 끝나면 하나의 병사 그룹이 완성됨
• 반환값으로 해당 그룹의 병사 수를 얻음