백준 1260 - DFS와 BFS

문제

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

1260번: DFS와 BFS

 

풀이

문제 조건 중

"방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" 를 만족하기 위해

인접 리스트 형식으로 입력을 받은 후 정렬을 해줘야 한다.

그 후 dfs와 bfs를 진행 하면 된다.

코드

python

from collections import deque
def dfs(v, visited):
    visited[v] = True
    print(v, end=' ')
    for nextNode in adjacency_list[v]:
        if not visited[nextNode]:
            dfs(nextNode, visited)
 
def bfs(v, visited):
    q = deque([v])
    visited[v] = True
    while q:
        v = q.popleft()
        print(v, end=' ')
        for nextNode in adjacency_list[v]:
            if not visited[nextNode]:
                q.append(nextNode)
                visited[nextNode] = True
 
# 입력
n, m, v = map(int, input().split())
adjacency_list = [[] for i in range(n + 1)]    # 인접 리스트 입력
for i in range(m):
    s, e = map(int, input().split())
    adjacency_list[s].append(e)
    adjacency_list[e].append(s)
 
for l in adjacency_list:
    l.sort()
 
visited = [False] * (n + 1)
dfs(v, visited)
visited = [False] * (n + 1)
print()
bfs(v, visited)

 

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
 
        StringTokenizer st = new StringTokenizer(input);
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
 
        List[] adjList = new List[n+1];
 
        for (int i=0; i<n+1; i++) {
            adjList[i] = new ArrayList<>();
        }
 
        for (int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
 
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
 
            adjList[s].add(e);
            adjList[e].add(s);
        }
 
        for (int i=1; i<=n; i++) {
            Collections.sort(adjList[i]);
        }
 
        boolean[] visited = new boolean[n+1];
 
        dfs(v, adjList, visited);
        System.out.println();
        visited = new boolean[n + 1];
        bfs(v, adjList, visited);
    }
 
    private static void dfs(int v, List<Integer>[] adjList, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");
 
        for (int nextNode : adjList[v]) {
            if (!visited[nextNode]) {
                dfs(nextNode, adjList, visited);
            }
        }
    }
 
    private static void bfs(int v, List<Integer>[] adjList, boolean[] visited) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
 
        while (!q.isEmpty()) {
            v = q.poll();
            visited[v] = true;
 
            System.out.print(v + " ");
            for (int nextNode : adjList[v]) {
                if (!visited[nextNode]) {
                    q.offer(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
 
 
    }
}