[Java] 백준 1260번 DFS와 BFS

 

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

1260번: DFS와 BFS

 

DFS와 BFS를 대표하는 기본문제로 구조를 익히는데 도움이 된다.

그래프를 저장하는 방법 중 인접행렬과 인접리스트를 사용하여 구현하였다:)

 

개인적으로는 인접행렬을 이용한 방식이 더 쉽다고 느꼈다!

 

- 인접행렬 이용

package com.dfs.bfs;
import java.io.*;
import java.util.*;

public class B1260 {
	static StringBuilder sb = new StringBuilder();
	static int N; // 정점의 개수
	static int M; // 간선의 개수
	static int V; // 시작 정점 번호
	static int[][] map; // 그래프
	static boolean[] visited; // 방문체크
	
	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());
		V = Integer.parseInt(st.nextToken());
		
		map = new int[N+1][N+1]; // 정점이 1부터 시작하기 때문에 +1을 해주었다.
		visited = new boolean[N+1];
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			map[x][y] = map[y][x] = 1; //연결되어있다는 것을 표시 -> 양방향이기 때문에 map[x][y] = map[y][x]
			// 단방향 -> map[x][y]만 사용
        }
		
		dfs(V);
		sb.append("\n");
		visited = new boolean[N+1];
		bfs(V);
		System.out.println(sb);
	}
	
	static void dfs(int node) {
		// 들어온 node를 방문처리해준다.
		visited[node] = true;
		sb.append(node + " ");
		// 연결된 node가 있는지 for문을 통해 확인하기
		for(int i=1; i<N+1; i++) {
			// 만약 node와 연결된 노드가 존재하고, 방문하지 않았을 경우
			if(map[node][i]==1 && !visited[i]) {
				// 재귀를 통해 방문
				dfs(i);
			}
		}
		
	}
	
	static void bfs(int node) {
		// node 방문처리
		visited[node] = true;
		// Queue에 node를 넣어줌
		Queue<Integer> q = new LinkedList<>();
		q.add(node);
		// Queue에 node가 존재하지 않을 때까지 반복
		while(!q.isEmpty()) {
			// Queue에 제일 처음 있는 node를 꺼냄
			int x = q.poll();
			sb.append(x + " ");
			// 꺼낸 node와 연결되어 있는 node 찾기
			for(int i=1; i<N+1; i++) {
				// 꺼낸 node와 연결되어 있고, 방문하지 않았다면
				if(map[x][i]==1 && !visited[i]) {
					// Queue에 꺼낸 node와 연결되어 있는 node를 넣어줌
					q.add(i);
					// 그 후 Queue에 넣은 node를 방문처리
					visited[i] = true;
				}
			}
		}
	}

}

 

- 인접리스트 이용

 

package com.dfs.bfs;
import java.io.*;
import java.util.*;
public class B1260_v2 {
	// 인접리스트로 DFS/BFS 풀이하기
	// 1. 간선 리스트 배열 생성 -> 초기화
	// 2. 간선 리스트에 양방향으로 노드 넣기
	
	static int N; // 정점의 개수
	static int M; // 간선의 개수
	static int V; // 시작 정점 번호
	static ArrayList<Integer>[] map; // 그래프
	static boolean[] visited; // 방문체크
	
	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());
		V = Integer.parseInt(st.nextToken());
		
		map = new ArrayList[N+1]; // 정점이 1부터 시작하기 때문에
		visited = new boolean[N+1];
		
		// 1번 정점부터 리스트를 만들어 map에 저장
		for(int i=1; i<=N; i++) {
			map[i] = new ArrayList<>();
		}
        
		// 연결된 노드들을 저장
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			// 양방향이기 때문에 밑에와 같이 넣어줌
			// 단방향일 경우 map[x].add(y)만 사용
			map[x].add(y);
			map[y].add(x);
		}
		// 정점번호가 작은 것부터 방문해야하기 때문에 각 리스트들을 정렬
		for(int i=1; i<=N; i++) {
			Collections.sort(map[i]);
		}
		dfs(V);
		Arrays.fill(visited, false);
		System.out.println();
		bfs(V);
	}
	// 밑의 dfs와 bfs는 위에 설명한 인접행렬과 같은 방식임
	private static void dfs(int node) {
		visited[node] = true;
		System.out.print(node + " ");
		
		for(int e : map[node]) {
			if(!visited[e]) {
				dfs(e);
			}
		}
	}
	
	private static void bfs(int node) {
		Queue<Integer> q = new LinkedList<>();
		q.add(node);
		visited[node] = true;
		
		while(!q.isEmpty()) {
			int x = q.poll();
			System.out.print(x + " ");
			for(int e : map[x]) {
				if(!visited[e]) {
					q.add(e);
					visited[e] = true;
				}
			}
		}
	}

}