백준 1260번
https://www.acmicpc.net/problem/1260
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
생각하기
DFS와 BFS의 개념을 다지기 위한 기초 문제이다.
나도 공부를 하면서 워낙 힘들었던 터라 개념설명은 힘들 것 같고..
그냥 정리만 하는걸로..
일단 DFS는 재귀나 stack을 주로 사용하고
BFS는 보통 LinkedList나 Queue를 사용한다.
여기서 내가 사용한 방법은 DFS는 재귀, BFS는 Queue를 사용했다.
DFS를 가장 쉽게 설명할 수 있는 말은 '한놈만 팬다' 이고
BFS를 가장 쉽게 설명할 수 있는 말은 '이놈패다가 저놈패는것(?)'이다.
이게 맞나?
본격적으로 문제를 풀이해보자면
방문한 노드를 기록할 수 있는 배열이 하나 필요하고,
간선을 기록하는 배열이 필요하다
나는 이 2개를 Visited_arr 과 Edge_arr로 만들었다.
Visited_arr은 방문의 여부만 따지면 되기 때문에 true/false로 기록했다. (boolean형)
Edge_arr은 당연히 int형
아, 여기서 또 생각해야 할 점이 Visited_arr의 사이즈가 1001로 되어있는데, 이는 노드(정점)의 숫자는 1부터 시작하지만
배열은 0부터 시작하기 때문에 사이즈를 맞추기위해서 1을 + 한 값으로 배열을 생성하는 것이다.
1000의 의미는 당연히 정점의 최대 갯수!
기본적인 배열에 담는 부분은 뛰어넘기로 하고,
DFS먼저 보자
DFS
먼저 시작은 첫번째 출발 노드를 알려줬으니 V를 이용해서 시작한다 ->DFS(V)
DFS가 시작되면 해당 노드 자체가 방문을 했다는 의미가 되니까
Visited_arr[start]에 해당하는 값을 true로 바꿔준다
참고로 boolean형 배열을 처음에 만들면 모두 false값으로 초기화 되어있다.
count는 재귀함수를 호출하면서 밑에 있는 반복문을 이용하게 되는데
최대한 반복횟수를 줄일 수 있도록 마지막에 DFS가 실행됬을 때, count 값과 노드의 갯수(N)가 같을 경우 곧바로 return을 하여 DFS를 종료시키도록 만들어줬다.
이제 아래에 있는 반복문을 보자.
for문에서 i값을 1부터 증가시켜서 노드최대값 N까지 증가시키며 반복한다.
이렇게 되면 start 방향에서 출발해서 다른 i값 노드로 가는 간선이 있는지 모두 체크하게 된다.
여기서 한놈만 패는 스타일이 나오는 것이다.
start 값이 정해지면 해당 start 값에서 출발하는 간선이 있는지 계속 찾는다.
그리고 간선을 찾았을 경우 i값을 DFS(i)로 해서 i 값이 start가 되게 만들어 DFS를 실행시키는 것이다.
이 과정을 계속 반복하면서 연결되는 간선을 타고 타고, 넘어가며 모든 노드를 방문해서
Visited_arr 배열이 모두 true가 되는 순간(Visited-arr[0]은 false) DFS는 끝나게 된다.
BFS
이제 여러 놈을 한번 동시에 패보자.
위에서 말했듯 BFS는 Queue를 이용한다.
Queue가 비었으면 모든 노드를 방문한 것이 되는 것이다.
DFS와 똑같이 BFS(V)로 시작해서
시작되는 start값을 먼저 que에 집어 넣는다.
이해 start 값을 다시 que에서 빼낸 값으로 바꿔주고
이 값을 시작점으로 i값을 증가시키며 노드를 찾는다
여기서 차이점이 드러나는데
DFS 였으면 i값이 start로 바뀌어 다음 노드로 넘어갔을 테지만
BFS는 start값은 그대로 두고 i값을 증가시켜서 계속 연결된 간선을 찾는다는 것이다.
여기서 연결되 있는 간선을 보고 노드 값을 찾아서 해당 노드값을 que에 넣는다
(첫번째 테스트케이스 기준)
처음 시작 하는 노드 1을 기준으로 보면 2 3 4와 연결되어 있으니
i값을 증가하면서 2 3 4 값을 que에 넣는다고 생각하면 된다.
해당 과정을 반복하고,que가 비어있을 때 까지 이 과정을 반복한다.
이렇게 되면 BFS가 종료된다.
TMI
어려운 것 같으면서도 쉬운것 같기도 하다
사실 어렵다기보다는 진짜 복잡한 것 같다..
이 문제를 풀려고 재귀관련된 문제와 공부를 다시 하고왔다ㅠㅠ
이렇게 성장하는거 아니겠나 싶다
머리가 조금만 더 좋았으면 좋았을텐데!!
난 왜 머리가 나쁠까!!
코드
import java.util.*; import java.io.*; public class Main { static int Edge_arr[][]; static boolean Visited_arr[]; static int N; static int M; static int V; static int count; static Queue<Integer> que = new LinkedList<>(); public static void BFS(int start) { que.offer(start); Visited_arr[start] = true; System.out.print(start + " "); while( !que.isEmpty() ) { start = que.poll(); for(int i=1; i<=N; i++) { if(Edge_arr[start][i] == 1 && Visited_arr[i] == false) { que.offer(i); Visited_arr[i] = true; System.out.print(i + " "); } } } } public static void DFS(int start) { Visited_arr[start] = true; System.out.print(start + " "); if(count == N) { return; } count ++; for(int i=1; i<=N; i++) { if(Edge_arr[start][i] == 1 && Visited_arr[i] == false) { DFS(i); } } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); V = Integer.parseInt(st.nextToken()); Edge_arr = new int[1001][1001]; Visited_arr = new boolean[1001]; for(int i=0; i<M; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); Edge_arr[x][y] = Edge_arr[y][x] = 1; } DFS(V); System.out.println(); Visited_arr = new boolean[1001]; BFS(V); } }
