링크
https://www.acmicpc.net/problem/1260
문제 설명
(정답률 37.255%)
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력 예제
4 5 1
1 2
1 3
1 4
2 4
3 4
출력 예제
1 2 4 3
1 2 3 4
정답 코드
-
우선 그래프를 나타내는 인접 리스트를 생성한다.
예제의 경우 다음과 같다.
{1=[2, 3, 4],
2=[1, 4],
3=[1, 4],
4=[1, 2, 3]}
방향이 없는 무방향 그래프이기 때문에 반대편 정점의 노드도 추가해준다. -
dfs의 경우 재귀를 이용하여 구현한다.
1 -> 2: 2를 방문한 다음 2의 인접 리스트를 확인한다. (2를 인자로 재귀 호출)
2= {1, 4}, 1은 방문했기 때문에 4을 방문한다.
1 -> 2 -> 4: 4의 인접 리스트 중 방문하지 않은 노드는 3이다. (4를 인자로 재귀 호출)
따라서 dfs의 결과는 1 -> 2 -> 4 -> 3이다. -
bfs는 큐를 이용한다.
1: 시작 노드인 1을 방문하고 1의 인접 리스트를 체크한다.
방문하지 않은 노드는 2, 3, 4이므로 순차적으로 큐에 추가한다.
1 -> 2: 큐의 첫번째 데이터인 2를 삭제하고 출력. 2의 인접리스트에서 방문하지 않은 노드는 없다.
1 -> 2 -> 3: 큐의 첫번째 데이터인 3을 삭제하고 출력. 3의 인접리스트에서 방문하지 않은 노드는 없다.
1 -> 2 -> 3 -> 4: 큐에서 4를 삭제 및 출력하고 반복을 중단한다.
import java.util.*;
import java.io.*;
public class Main {
//인접리스트를 만들 HashMap
static HashMap<Integer, List<Integer>> adjList;
//방문 노드를 체크할 배열
static boolean[] visit;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
//HashMap 생성 및 초기화
adjList = new HashMap<>();
for (int i = 1; i <= N; i++) {
adjList.put(i, new ArrayList<>());
}
//인접 리스트 생성
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
adjList.get(a).add(b);
adjList.get(b).add(a);
}
// 오름차순 정렬
for (List<Integer> value : adjList.values()) {
Collections.sort(value);
}
//visit은 메서드 실행전에 초기화
visit = new boolean[N + 1];
dfs(V);
visit = new boolean[N + 1];
sb.append("\n");
bfs(V);
System.out.println(sb);
}
//깊이 우선 탐색 메서드
private static void dfs(int node) {
//인자로 받은 node 출력
sb.append(node).append(" ");
//방문 처리
visit[node] = true;
//방문한 노드의 리스트를 체크한다
for (Integer i : adjList.get(node)) {
//방문하지 않은 노드를 만날 경우
//재귀 호출
if (!visit[i]) {
dfs(i);
}
}
}
//넓이 우선 탐색 메서드
private static void bfs(int node) {
Queue<Integer> queue = new LinkedList<>();
//인자로 받은 node 방문 처리
visit[node] = true;
//큐에 node 추가
queue.add(node);
//큐가 빌 때까지 반복
while (!queue.isEmpty()) {
//큐의 첫번째 데이터 반환 및 제거
int newNode = queue.poll();
//반환한 노드를 출력
sb.append(newNode).append(" ");
//newNode의 리스트를 체크한다
for (Integer i : adjList.get(newNode)) {
//방문하지 않은 노드를 큐에 추가 및 방문 처리
if (!visit[i]) {
visit[i] = true;
queue.add(i);
}
}
}
}
}정리
그래프 문제는 낯설어서 어려웠다.
dfs, bfs의 개념이 대강만 있어서 실제로 적용하려니 쉽지 않았다.
우선 그래프를 구현하는 방법도 인접 행렬, 인접 리스트 2가지 방법이 있었다.
인접 리스트는 위에서 보인 방법이고 인접 행렬은 이차원 배열을 이용한 방법이다.
//인접 행렬 구현
for(int i = 0 ; i < line ; i ++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[a][b] = arr[b][a] = 1;
}
//[[0,0,0,0,0],
//[0,0,1,1,1],
//[0,1,0,0,1],
//[0,1,0,0,1],
//[0,1,1,1,0]]시간복잡도 관점에서 각각의 장단점이 있다고 한다.
풀이는 인접 행렬이란 개념이 잘 와닿지 않아서
그나마 직관적인 인접 리스트로 구현했다.
