[백준/1260/Java] DFS와 BFS

 

문제:

 

www.acmicpc.net/problem/1260

 

1260번: DFS와 BFS

 

문제를 먼저 풀고 오시는 것을 추천합니다.

이 문제는 제목에도 표현되어 있지만 DFS, BFS 알고리즘을 사용할 줄 아는지 물어보는 문제입니다.

 

문제분석

그래프를 DFS, BFS로 탐핵한 결과를 출력하라는 문제입니다.

단, 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문하시면 되고 더이상 방문할 수 있는 점이 없으면 종료하면 됩니다.

이번 그래프는 양방향이며, DFS, BFS 방문순서를 이해하기에 좋은 문제입니다.

 

입력

첫째줄에 정점의 개수 N(1 <= N <= 1,000), 간선의 개수 M(1 <= M <= 10,000), 탐색을 시작할 정점의 번호 V가 주어집니다.

다음 M개의 줄에 두 정점의 번호가 주어집니다. 간선의 방향은 양방향입니다.

 

출력

첫째줄에 DFS로 방문한 정점을 순서대로 출력합니다.

둘째줄에 BFS로 방문한 정점을 순서대로 출력합니다.

 

풀이

입력에서 정점 2개가 주어지므로 양방향 간선정보를 저장하시면 됩니다.

간혹 단방향 간선정보만 저장하게 되면 문제를 틀리게 되오니 조심하시기 바랍니다.

이 문제는 인접 행렬(2차원 배열), 인접 리스트(List 배열) 중 편하신 자료구조로 저장하시면 됩니다.

그리고 가장 낮은 수부터 이동해야 하므로 인접 리스트의 경우 정렬을 하셔야 합니다.

정점의 개수가 최대 1000개라서 공간복잡도가 높지 않아서 메모리를 많이 차지하지 않습니다.

 

각 정점에서 연결된 정점 중 가장 낮은 수로 이동하도록 DFS(깊이우선탐색), BFS(너비우선탐색)으로 구현하시면 됩니다.

 

예제풀이

첫번째 예제를 보시면 4개의 정점, 5개의 간선이 주어지고 시작점은 1입니다.

 

그래프

시작점을 짙은 파랑색으로 표시하였습니다. 

 

DFS(깊이우선탐색)

첫번째 이동

1번 노드에서 연결된 노드는 2, 3, 4입니다.

가장 낮은 수는 2이므로 2번 노드로 이동합니다.

 

 

두번째 이동

DFS이므로 이동한 2번 노드에서 연결된 노드를 검색하면 1, 4번 노드가 있습니다.

1번 노드는 이미 방문하였으므로 4번 노드로 이동합니다.

 

세번째 이동

4번 노드에서 연결된 노드는 1, 2, 3번 노드입니다.

1, 2 번 노드는 이미 방문하였으므로 3번 노드로 이동합니다.

 

마무리

3번 노드에서 연결된 노드는 1, 4번 노드입니다.

모두 방문하였으므로 지금까지 이동한 노드를 다시 거꾸로 이동하게 됩니다.

그러나 3 -> 4 -> 2 -> 1번 노드를 되돌아가면서 방문을 하지 않은 노드를 찾지만 존재하지 않으므로 종료하게 됩니다.

 

BFS(너비우선탐색)

첫번째 큐 삽입

1번 노드에서 연결된 노드는 2, 3, 4번 노드입니다.

가장 낮은 2번 노드를 큐에 넣습니다.

두번째 큐 삽입

1번 노드에서 2번 노드를 넣었으므로 그 다음 작은 번호인 3번 노드를 큐에 넣습니다.

 

 

세번째 큐 삽입

1번 노드에서 2, 3번 노드를 넣었으므로 마지막으로 남은 4번 노드를 큐에 넣습니다.

 

큐 2번 노드 pop

현재 큐에 2, 3, 4번 노드가 들어있습니다.

이제 1번 노드에서 모든 노드를 방문하였으므로 큐에서 하나 꺼내서 확인합니다.

2번 노드에서 연결된 1, 4번 노드는 이미 방문하였으므로 큐에 더이상 넣는 것은 없습니다.

 

큐 3번 노드 pop

큐에서 하나 꺼내서 3번 노드를 확인합니다.

3번 노드에서 연결된 1, 4번 노드는 이미 방문하였으므로 큐에 더이상 넣는 것은 없습니다.

큐 4번 노드 pop

큐에서 마지막 남아있는 4번 노드를 꺼내서 확인합니다.

4번 노드에서 연결된 1, 2, 3번 노드는 모두 방문하였므로 더이상 큐에 넣는 것은 없습니다.

 

 

소스

인접리스트로 풀은 DFS와 BFS 소스입니다.

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

public class Main
{
	static int N;
	static int M;
	static int V;

	static List<Integer>[] line;

	static int index = 0;
	static int[] visited = new int[1001];
	static boolean isEnd = false;

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();

		StringTokenizer st = new StringTokenizer(input);
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());

		line = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++)
		{
			line[i] = new ArrayList<Integer>();
		}

		String[] inputs = new String[2];
		for (int i = 1; i <= M; i++)
		{
			input = br.readLine();
			inputs = input.split(" ");
			line[Integer.parseInt(inputs[0])].add(Integer.parseInt(inputs[1]));
			line[Integer.parseInt(inputs[1])].add(Integer.parseInt(inputs[0]));
		}

		for (int i = 1; i <= N; i++)
		{
			Collections.sort(line[i]);
		}

		// DFS
		visited[V] = 1;
		System.out.print(V + " ");
		index++;
		dfs(V);

		for (int i = 1; i <= N; i++)
		{
			visited[i] = 0;
		}

		System.out.println();

		// BFS
		bfs(V);
		System.out.println();
	}

	private static void bfs(int node)
	{
		Queue<Integer> queue = new LinkedList<Integer>();

		queue.add(node);
		visited[node] = 1;
		index = 1;
		while (queue.isEmpty() == false)
		{
			node = queue.remove();
			System.out.print(node + " ");
			for (int next : line[node])
			{
				if (visited[next] == 0)
				{
					index++;
					visited[next] = 1;
					queue.add(next);
				}
			}
		}
	}

	private static void dfs(int node)
	{
		for (int next : line[node])
		{
			if (visited[next] == 0)
			{
				System.out.print(next + " ");

				index++;
				visited[next] = 1;
				dfs(next);
			}
		}
	}
}

 

양방향 그래프 문제를 풀어보았습니다.

단방향 그래프 문제인 효율적인 해킹 문제로 같이 풀어보시는 것을 추천드립니다.

 

관련글:

2021/02/01 - [Algorithm] - [백준/1325/Java] 효율적인 해킹 - BFS/DFS 풀이

[백준/1325/Java] 효율적인 해킹 - BFS/DFS 풀이

 

2021/02/09 - [Algorithm] - [백준/1012/Java] 유기농 배추 - BFS 풀이

[백준/1012/Java] 유기농 배추 - BFS 풀이