BOJ1260 DFS와 BFS

<Solution>

1. 두개의 노드가 연결되어 있다는 어찌 표현할지 -> 2차원 배열에 연결되어 있는 노드는 1로 표현

1,2가 연결인 경우

0 1 0 0

1 0 0 0 이런식으로

2. visit은 방문한 노드만 체크 -> 1차원 배열로 노드만

---

<Source Code>

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 BOJ1260_BFSDFS {
	
	static int[] visit;
	static int[][] map;
	static int N, M;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		// 인접한 곳 1로 표시
		map = new int[N+1][N+1];
		visit = new int[N+1];
		for(int i = 0; i < M; i++)
		{
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			map[a][b] = 1;
			map[b][a] = 1;
		}
		dfs(V);
		System.out.println();
		visit = new int[N+1];
		bfs(V);
	}
	
	public static void dfs(int V) {
		System.out.printf(V + " ");
		visit[V] = 1;
		for(int i = 1; i <= N; i++) {
			// 이미 방문한 노드이거나 인접한 곳이 아닌경우 건너뛰기
			if(visit[i] == 1 || map[V][i] == 0)
				continue;
			dfs(i);
		}
	}
	
	public static void bfs(int V) {
		Queue<Integer> q = new LinkedList<>();
		q.add(V);
		visit[V] = 1;
		while(!q.isEmpty()) {
			V = q.poll();
			System.out.printf(V + " ");
			for(int i = 1; i <= N; i++) {
				if(visit[i] == 1 || map[V][i] == 0)
					continue;
				q.add(i);
				visit[i] = 1;
			}
		}
	}
}