[백준1260] DFS와 BFS

DFS

 

		visit[start] = true;
		sb.append(start + " ");
		dfs(start, board);
		sb.append("\n");
	}
	static void dfs(int node, int[][] board) {
		
		//recursive case
		for (int i=1; i<=N; i++) {
			if (!visit[i] && board[node][i]==1) {
				visit[i] = true;
				sb.append(i + " ");
				dfs(i, board);
			}
		}
	}

*트리 그려놓고 차근히 진행

 

 

BFS

		bfs(start, board);
        
static void bfs(int node, int[][] board) {
		
		Queue<Integer> queue = new LinkedList<>();
		queue.add(node);
		visit2[node] = true;
		sb.append(node + " ");
		while(queue.size()!=0) {
			
			int visited = queue.poll();
			for (int i=1; i<=N; i++) {
				
				if(!visit2[i] && board[visited][i]==1) {
					queue.add(i);
					visit2[i] = true;
					sb.append(i + " ");
				}
			}
		}
	}

*주의* : 

큐에 넣는 행위를 방문(visit check)이라고 하자. 큐에서 빼는 행위를 방문(visit check)이라고 하면 큐의 작업프로세스 중 문제가 발생

 

*트리 그려놓고 진행하자.