[백준 JAVA & Python] 1260 DFS와 BFS

문제

---

1260번: DFS와 BFS (acmicpc.net)

1260번: DFS와 BFS

 

bfs, dfs를 연습해보기 좋은 기본문제이다.

 

풀이방법

---

• 무방향 그래프이기 때문에, 배열 양쪽에 값을 넣어주는 것이 포인트이다.
  • list[to].add(from);
    list[from].add(to);
• dfs는 순열을 사용해서, bfs는 큐를 사용해서 구현하였다.

코드

 

---

 

• 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 ArrayList<Integer> list[];
	static int N,M;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sb = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(sb.nextToken());
		M = Integer.parseInt(sb.nextToken());
		int V = Integer.parseInt(sb.nextToken());
		
		list = new ArrayList[N+1];
		for(int i=1; i<N+1; i++) {
			list[i]=new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			sb = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(sb.nextToken());
			int to = Integer.parseInt(sb.nextToken());
			list[to].add(from);
			list[from].add(to);
		}
		
		for(int i=1; i<=N; i++) {
			Collections.sort(list[i]);
		}
		
		boolean[] visit=new boolean[N+1];
		dfs(V,visit);
		System.out.println();
		visit=new boolean[N+1];
		bfs(V,visit);
		
		
	}
	
	static void dfs(int start, boolean[] visit) {
		System.out.print(start+" ");
		visit[start]=true;
		
		for(int i=0; i<list[start].size(); i++) {
			if(visit[list[start].get(i)]==false) {
				dfs(list[start].get(i),visit);
				}
			}
		
		return;
	}
	
	static void bfs(int start,boolean[] visit) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);
		visit[start]=true;
		
		while(!queue.isEmpty()) {
			int c=queue.poll();
			System.out.print(c+" ");
			for(int i=0; i<list[c].size(); i++) {
				if(visit[list[c].get(i)]==false) {
					visit[list[c].get(i)]=true;
					queue.offer(list[c].get(i));
				}
			}

		}
		
	}


}

• Python

from collections import deque

n,m,v=map(int,input().split())
visit=[False]*(n+1)
graph=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1):
    graph[i].sort()

def dfs(start):
    visit[start]=True
    print(start,end=' ')
    for i in graph[start]:
        if visit[i]==False:
            dfs(i)

def bfs(start):
    visit[start]=True
    que = deque()
    que.append(start)
    while(que):
        n = que.popleft()
        print(n,end=' ')
        for i in graph[n]:
            if visit[i]==False:
                que.append(i)
                visit[i]=True
dfs(v)
visit=[False]*(n+1)
print('')
bfs(v)