[Algorithm] 99클럽 코테 스터디 6일차 TIL | 백준_DFS와 BFS(1260번)

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

---

dfs와 bfs의 개념만 알고 있다면 풀 수 있는 문제

나는 2차원 배열에 입력값을 그대로 담아

간선 리스트를 사용하여 그래프를 표현하였다.

 

문제에 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다고 되어있어

2차원 배열을 정렬하여 문제를 풀었다.

for(int i = 0; i < M; i++){
    st = new StringTokenizer(br.readLine());
    map[i][0] = Integer.parseInt(st.nextToken());
    map[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(map, (a,b) -> {
    if(a[0] == b[0]){
        return a[1] - b[1];
    }
    return a[0] - b[0];
});

한 가지 간과하고 있던 문제는

입력값이 

5 3 1

1 5

3 5

5 2

로 들어올 때다.

 

기존 풀이에서 위와 같이 정렬했을 때 결과는 1 5 2 3이 나와야 되는데 1 5 3 2 가 나왔다

for(int i = 0; i < M; i++){
    st = new StringTokenizer(br.readLine());
    map[i][0] = Integer.parseInt(st.nextToken());
    map[i][1] = Integer.parseInt(st.nextToken());
    if(map[i][0] > map[i][1]){
        int temp = map[i][0];
        map[i][0] = map[i][1];
        map[i][1] = temp;
    }
}

그래서 배열의 첫번째 값에 가장 작은 값이 들어올 수 있도록 설정해주었다.

이렇게 하면 원하는 값을 얻을 수 있다,!

 

전체풀이

import java.util.*;
import java.io.*;
class Main{
    static StringBuilder answer = new StringBuilder();
    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());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        map = new int[M][2];
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            map[i][1] = Integer.parseInt(st.nextToken());
            if(map[i][0] > map[i][1]){
                int temp = map[i][0];
                map[i][0] = map[i][1];
                map[i][1] = temp;
            }
        }
        Arrays.sort(map, (a,b) -> {
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        visited = new boolean[N+1];
        dfs(V, M);
        visited = new boolean[N+1];
        bfs(V, M);

        System.out.println(answer.toString());
    }

    public static void dfs(int n, int M){
        answer.append(n).append(" ");
        visited[n] = true;

        for(int i = 0; i < M; i++){
            if(!visited[map[i][1]] && map[i][0] == n){
                dfs(map[i][1], M);
            }else if(!visited[map[i][0]] && map[i][1] == n){
                dfs(map[i][0], M);
            }
        }
    }

    public static void bfs(int n, int M){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        answer.append("\n").append(n);

        while(!queue.isEmpty()){
            int num = queue.poll();
            visited[num] = true;
            for(int i = 0; i < M; i++){
                if(!visited[map[i][1]] && map[i][0] == num){
                    queue.add(map[i][1]);
                    visited[map[i][1]] = true;
                    answer.append(" ").append(map[i][1]);
                }else if(!visited[map[i][0]] && map[i][1] == num){
                    queue.add(map[i][0]);
                    visited[map[i][0]] = true;
                    answer.append(" ").append(map[i][0]);
                }
            }
        }
    }
}

 

다른 분들 풀이가 대부분 인접 행렬을 사용하여 풀었길래!

이 방법으로도 풀이를 해봤다.

import java.util.*;
import java.io.*;
class Main{
    static StringBuilder answer = new StringBuilder();
    static boolean[][] graph;
    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());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        graph = new boolean[N+1][N+1];
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            graph[n1][n2] = true;
            graph[n2][n1] = true;
        }

        visited = new boolean[N+1];
        dfs(V, N);
        visited = new boolean[N+1];
        bfs(V, N);

        System.out.println(answer.toString());
    }

    public static void dfs(int n, int N){
        answer.append(n).append(" ");
        visited[n] = true;

        for(int i = 1; i <= N; i++){
            if(graph[n][i] && !visited[i]){
                dfs(i, N);
            }
        }
    }

    public static void bfs(int n, int N){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        answer.append("\n");

        while(!queue.isEmpty()){
            int num = queue.poll();
            visited[num] = true;
            answer.append(num).append(" ");
            for(int i = 1; i <= N; i++){
                if(graph[num][i] && !visited[i]){
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

간-결..

 

위에가 인접행렬, 아래가 간선리스트로 풀이한 결과다.