백준 16947번 서울 지하철 2호선

문제

나의 풀이

import java.util.*;

public class Main {
    static ArrayList<Integer>[] a;
    static int check[];
    static int dist[];
    static int go(int x, int p) {
        // -2 : 사이클을 찾았지만, 포함되지 않은 경우
        // -1 : 사이클을 찾지 못한 경우
        // 0~n-1 : 사이클을 찾았고 사이클의 시작점
        if(check[x] == 1) { // 사이클을 찾은 경우
            return x; // 시작점을 리턴
        }
        check[x] = 1;
        for(int y : a[x]) {
            if(y == p) { // 이미 방문한 경우
                continue;
            }
            int res = go(y, x);
            if(res == -2) { // 사이클에 포함되지 않는 경우
                return -2;
            }
            if(res >= 0) { // 사이클에 포함되는 경우
                check[x] = 2; // 사이클의 일부임을 표시
                if(x == res) { // 한바퀴 돌아서 사이클의 시작점에 도달
                    return -2; // 다음 정점부터는 사이클이 아님
                } else {
                    return res;
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = new ArrayList[n];
        dist = new int[n];
        check = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = new ArrayList<>();
        }
        for(int i = 0; i < n; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            a[u].add(v);
            a[v].add(u);
        }
        go(0, -1); // 순환선 찾기
        // 각 역들의 순환선과 거리 찾기(bfs)
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            if(check[i] == 2) { // 순환선에 포함된 정점인 경우
                dist[i] = 0;
                q.add(i);
            } else {
                dist[i] = -1;
            }
        }
        while(!q.isEmpty()) {
            int x = q.poll();
            for(int y : a[x]) {
                if(dist[y] == -1) { // 순환선에 포함되어 있지 않고, 계산되지 않은 경우
                    q.add(y);
                    dist[y] = dist[x] + 1;
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            System.out.print(dist[i] + " ");
        }
        System.out.println();
    }
}

Two Dots 문제에서 했던 것 처럼 사이클을 찾고, 사이클을 찾은 경우 사이클의 시작점을 리턴하게 하고, 사이클을 찾기는 했으나 해당 정점이 사이클에 포함되지 않은 경우 -2를 리턴하게 하여 구분할 수 있도록 한다.
그런 다음 bfs 알고리즘을 통해서 거리를 구해주면 된다. 사이클에 포함되는 정점들은 큐의 시작점으로 넣어줘서 거리는 0으로 지정한다. 그외는 dist를 -1로 지정해주어 bfs로 거리를 계산할 수 있도록 한다.

결과

백준 16940번 BFS 스페셜 저지

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer>[] a = new ArrayList[n];
        int b[] = new int[n];
        int order[] = new int[n];
        boolean check[] = new boolean[n];
        for(int i = 0; i < n; i++) {
            a[i] = new ArrayList<>();
        }
        for(int i = 0; i < n - 1; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            a[u].add(v);
            a[v].add(u);
        }
        for(int i = 0; i < n; i++) {
            b[i] = sc.nextInt() - 1;
            order[b[i]] = i; // 각 정점의 탐색 순서 저장
        }
        for(int i = 0; i < n; i++) {
            Collections.sort(a[i], new Comparator<Integer>() { // 탐색 순서를 기준으로 인접 리스트 정렬
                public int compare(Integer u, Integer v) {
                    if(order[u] < order[v]) {
                        return -1;
                    } else if(order[u] == order[v]) {
                        return 0;
                    } else {
                        return 1;
                    }
                }
            }); 
        }
        
        // bfs 탐색하며 순서 bfs_order에 저장
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        check[0] = true;
        ArrayList<Integer> bfs_order = new ArrayList<>();
        while(!q.isEmpty()) {
            int x = q.poll();
            bfs_order.add(x); // 탐색 순서 저장
            for(int y : a[x]) {
                if(check[y] == false) {
                    check[y] = true;
                    q.add(y);
                }
            }
        }
        
        boolean ok = true;
        for(int i = 0; i < n; i++) { // 올바른 순서인지 검사
            if(bfs_order.get(i) != b[i]) {
                ok = false;
            }
        }
        if(ok) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

입력으로 주어진 순서를 이용해서 인접 리스트를 정렬한 다음 이 순서로 BFS 탐색을 진행하게 해서 올바른 것인지 판단한다. order 배열에 각 정점의 탐색 순서를 저장하고 인접 리스트를 order 탐색 순서에 따라 정렬을 시킨 다음 bfs 탐색을 하면서 bfs_order 리스트에 정점을 추가시켜준다. 그런 다음 bfs_order의 순서가 입력 받았던 순서와 같은 경우 올바른 것이기 때문에 1을 출력하고 그렇지 않은 경우 0을 출력한다.

결과

백준 16964번 DFS 스페셜 저지

문제

나의 풀이

import java.util.*;

public class Main {
    static ArrayList<Integer>[] a;
    static ArrayList<Integer> dfs_order = new ArrayList<>();
    static boolean check[];
    static void dfs(int x) {
        if(check[x]) {
            return;
        }
        dfs_order.add(x); // 탐색 순서 저장
        check[x] = true;
        for(int y : a[x]) {
            dfs(y);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = new ArrayList[n];
        check = new boolean[n];
        int b[] = new int[n];
        int order[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = new ArrayList<>();
        }
        for(int i = 0; i < n - 1; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            a[u].add(v);
            a[v].add(u);
        }
        for(int i = 0; i < n; i++) {
            b[i] = sc.nextInt() - 1;
            order[b[i]] = i; // 각 정점의 탐색 순서 저장
        }
        for(int i = 0; i < n; i++) {
            Collections.sort(a[i], new Comparator<Integer>() { // 탐색 순서를 기준으로 인접 리스트 정렬
                public int compare(Integer u, Integer v) {
                    if(order[u] < order[v]) {
                        return -1;
                    } else if(order[u] == order[v]) {
                        return 0;
                    } else {
                        return 1;
                    }
                }
            }); 
        }
        
        // dfs 탐색하며 순서 dfs_order에 저장
        dfs(0);
        
        boolean ok = true;
        for(int i = 0; i < n; i++) { // 올바른 순서인지 검사
            if(dfs_order.get(i) != b[i]) {
                ok = false;
            }
        }
        if(ok) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

입력으로 주어진 순서를 이용해서 인접 리스트를 정렬한 다음 이 순서로 DFS 탐색을 진행해서 올바른 것인지 판단한다.

결과

백준 2146번 다리 만들기

문제

나의 풀이

import java.util.*;

public class Main {
    static class Pair {
        int x;
        int y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static final int dx[] = { 0, 0, 1, -1 };
    public static final int dy[] = { 1, -1, 0, 0 };
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[][] = new int[n][n];
        int d[][] = new int[n][n];
        int g[][] = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        // 각 섬들 그룹 번호 메기기
        int count = 0; 
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(a[i][j] == 1 && g[i][j] == 0) {
                    Queue<Pair> q = new LinkedList<Pair>();
                    g[i][j] = ++count;
                    q.add(new Pair(i, j));
                    while(!q.isEmpty()) {
                        Pair p = q.poll();
                        int x = p.x;
                        int y = p.y;
                        for(int k = 0; k < 4; k++) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if(0 <= nx && nx < n && 0 <= ny && ny < n) {
                                if(a[nx][ny] == 1 && g[nx][ny] == 0) {
                                    q.add(new Pair(nx, ny));
                                    g[nx][ny] = count;
                                }
                            }
                        }
                    }
                }
            }
        }
        
        // 거리 계산 (섬을 확장하는 방식으로)
        Queue<Pair> q = new LinkedList<Pair>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                d[i][j] = -1;
                if(a[i][j] == 1) {
                    q.add(new Pair(i, j));
                    d[i][j] = 0;
                }
            }
        }
        while(!q.isEmpty()) {
            Pair p = q.poll();
            int x = p.x;
            int y = p.y;
            for(int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if(d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        g[nx][ny] = g[x][y];
                        q.add(new Pair(nx, ny));
                    }
                }
            }
        }
        
        int answer = -1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < 4; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(0 <= x && x < n && 0 <= y && y < n) {
                        if(g[i][j] != g[x][y]) { // 각 칸의 인접한 칸들 중 그룹 번호가 다른 경우 -> 다리 연결 가능
                            if(answer == -1 || answer > d[i][j] + d[x][y]) {
                                answer = d[i][j] + d[x][y]; // 각 거리들 중 최솟값 구하기
                            }
                        }
                    }
                }
            }
        }
        System.out.println(answer);
    }
}

각각의 섬을 시작점에 넣은 다음 거리를 구하는 방식으로 문제를 해결할 수 있다.
인접한데 그룹 번호가 서로 다르면 그 둘을 연결하면 다리가 되므로 그 거리의 최솟값을 구하면 정답이 된다.

결과