백준 1260번: DFS와 BFS

1. 문제

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

 

2. 해결법

DFS와 BFS를 기본적으로 다룰 수 있는 문제

기본적인 이해만 한다면 해결가능

초짜라서 이해하는데 겁나 오래 걸림 ;ㅅ;

 

3. 코드

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

public class Main {
    static void dfs(int V, ArrayList<Integer>[] link, boolean[] visited, StringBuilder sb) {
		if(visited[V]) return; // 방문했으면 return
		
		visited[V] = true;
		sb.append(V + " ");
		
		for(int i:link[V]) {
			if(!visited[i]) {
				dfs(i, link, visited, sb);
			}
		}
	}
	
	static void bfs(int V, ArrayList<Integer>[] link, boolean[] visited, StringBuilder sb) {
		Queue<Integer> q = new LinkedList<Integer>(); // 담을 큐 선언 및 초기화
		visited[V] = true;
		q.add(V);
		
		while(!q.isEmpty()) { // 큐가 빌 때까지
			int node = q.poll(); // 가져왕
			sb.append(node + " ");
			
			for(int i:link[node]) {
				if(!visited[i]) {
					visited[i] = true;
					q.add(i);
				}
			}
		}
	}
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 한 줄 입력
		StringTokenizer str = new StringTokenizer(br.readLine()); // 토큰단위 파싱
		int N = Integer.parseInt(str.nextToken()); // 정점 갯수
		int M = Integer.parseInt(str.nextToken()); // 간선 갯수
		int V = Integer.parseInt(str.nextToken()); // 탐색을 시작할 정점 번호
		
		ArrayList<Integer>[] link = new ArrayList[N+1]; // 연결된 노드를 저장할 list 선언
		
		for(int i=0; i<link.length; i++) {
			link[i] = new ArrayList<Integer>(); // list 초기화
		}
		
		for(int i=0; i<M; i++) {
			str = new StringTokenizer(br.readLine()); // 계속 입력받음
			int n1 = Integer.parseInt(str.nextToken());
			int n2 = Integer.parseInt(str.nextToken());
			
			link[n1].add(n2); // 저장
			link[n2].add(n1);
		}
		br.close(); // bufferedreader 닫아주기
		
		// 자식이 여러 개일 때, 번호가 작은 것부터 방문하기 때문에 오름차순 정렬
		for(int i=0; i<link.length; i++) {
			Collections.sort(link[i]); // link[i] 줄을 정렬
		}
		
		boolean[] visited = new boolean[N+1]; // 방문 여부
		StringBuilder sb = new StringBuilder();
		
		dfs(V, link, visited, sb); // dfs 탐색 시작
		System.out.println(sb);

		sb.delete(0, sb.length()); // sb 초기화
		Arrays.fill(visited, false); // 방문여부도 다시 false로
		
		bfs(V, link, visited, sb); // bfs 탐색 시작
		System.out.println(sb);
	}
}

주석으로 나름 자세히 설명해뒀음.

 

+백준은 class이름 Main으로 해야되고, 선처리안하면 런타임에러뜨네요.