[Java/Python] 백준 1260번 - DFS와 BFS

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

1260번: DFS와 BFS

 

혼자 힘으로 풀었는가? : X
(내가 쓴 글 봤음)

알고리즘 유형
 - 그래프 이론
 - 그래프 탐색
 - 너비 우선 탐색
 - 깊이 우선 탐색

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

---

단순한 DFS / BFS 문제였다.

 

맨 처음 일단 문제를 아 DFS는 재귀적으로 풀고 BFS는 큐를 이용해서 풀어야겠다.

 

라고 까진 생각 했다.

 

하지만 구현하는건 다른 문제였고 결국 나는 이전에 내가 작성한 글을 참고로 다시 공부한단 생각으로 코드를 작성했다.

 

2022.08.01 - [Algorithm/이것이 코딩테스트다] - [Python][이코테] DFS

[Python][이코테] DFS

 

2022.08.02 - [Algorithm/이것이 코딩테스트다] - [Python][이코테] BFS

[Python][이코테] BFS

 

 

(Python 코드)

import sys
from collections import deque
q = deque()
input = sys.stdin.readline

n, m, v = map(int, input().split())
graph = [ [] for i in range(n+1)]
visited_dfs = [False] * (n+1)
visited_bfs = [False] * (n+1)

def dfs(now):
  visited_dfs[now] = True
  print(now, end=' ')
  graph[now].sort()
  for i in graph[now]:
    if not visited_dfs[i]:
      dfs(i)
      
def bfs(now):
  visited_bfs[now] = True
  q.append(now)
  while q:
    v = q.popleft()
    print(v, end=' ')
    graph[v].sort()
    for i in graph[v]:
      if not visited_bfs[i]:
        q.append(i)
        visited_bfs[i] = True
  
for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

dfs(v)
print()
bfs(v)

 

(Java 코드)

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

public class Main {

	static boolean [] visited_dfs;
	static boolean [] visited_bfs;
	static ArrayList<Integer>[] graph;
	static int n, m, v;
	static Queue<Integer> q = new LinkedList<>();

	public static void main(String[] args) throws IOException  {
		// TODO Auto-generated method stub

		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());

		graph = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			graph[i] = new ArrayList<>();
		}

		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			graph[a].add(b);
			graph[b].add(a);
		}

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

		visited_dfs = new boolean[n+1];
		visited_bfs = new boolean[n+1];

		dfs(v);
		System.out.println();
		bfs(v);
	}

	private static void dfs(int now) {
		// TODO Auto-generated method stub
		visited_dfs[now] = true;
		System.out.print(now+" ");
		for(int next: graph[now]) {
			if(!visited_dfs[next]) {
				dfs(next);
			}
		}
	}


	private static void bfs(int now) {
		// TODO Auto-generated method stub
		visited_bfs[now] = true;
		q.add(now);
		while(!q.isEmpty()) {
			int v = q.poll();
			System.out.print(v+" ");
			for(int next: graph[v]) {
				if( visited_bfs[next] == false) {
					q.add(next);
					visited_bfs[next] = true;
				}
			}
		}

	}
}