mingssssss

1. 문제

https://www.acmicpc.net/problem/1260

2. 코드

package mymain;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1260 {
	
	static int N;
	static int M;
	static int v;
	static int[][] list; 
	static boolean[] visited;
	static Queue<Integer> q;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		v = Integer.parseInt(st.nextToken());
		
		list = new int[N + 1][N + 1];
		visited = new boolean[N + 1];
		q = new LinkedList<>();
		
		for (int i = 0; i < M; i++) {
			
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			list[r][c] = 1;
			list[c][r] = 1;
		}
		// 양방향 인접 행렬 생성 종료
		
		dfs(v);
		System.out.println();
		bfs(v);
		
		
		
		
		
		
		// 출력
//		for (int i = 1; i < N + 1; i++) {
//			for (int j = 1; j < N + 1; j++) {				
//				System.out.printf("%d ", list[i][j]);
//			}
//			System.out.println();
//		}
	}
	
	private static void dfs(int v) {		
		
		visited[v] = true;
		System.out.print(v + " ");
		
		for (int i = 1; i < N + 1; i++) {
			
			if (list[v][i] == 1 && visited[i] == false) {
				dfs(i);
			}
		}
		
	}
	
	private static void bfs(int v) {
		
		visited = new boolean[N + 1];
		visited[v] = true;
		
		q.add(v);
		
		while (!q.isEmpty()) {
						
			int next = q.poll();
			
			System.out.print(next + " ");
			
			for (int i = 1; i < N + 1; i++) {
				
				if (visited[i] == false && list[next][i] == 1) {
					
					visited[i] = true;
					q.add(i);
				}
			}
		}
 	}

}

3. 리뷰

모든 dfs문제는 bfs로 변환해서 풀 수 있다고 굳게 믿고(자기 합리화..)

dfs 문제는 bfs로 변환해서 풀어왔지만.. 결국 dfs로만 풀 수 있는 문제의 발견과

재귀의 이해 때문에 결국 dfs 공부를 시작하게 됐다..

dfs 역시 bfs와 동일한 로직으로 진행되지만, dfs는 깊이 우선 탐색으로 진행되고

재귀로 구현하는 차이점이 있다.

dfs에 시작 노드를 추가하고 dfs를 시작한다.

visited 함수에 v를 방문 처리하고 해당 노드를 출력한다.

이후 리스트를 순회하면서 방문하지 않았고, 해당 노드가 1이라면

그 인덱스를 dfs에 넣고 돌려준다.

로직 자체는 bfs보다 훨씬 간단하지만 재귀 함수라 이해가 필요한 것 같다.