[BOJ - JAVA] 22868 - 산책 (BFS)

# 주소

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

22868번: 산책 (small)

# 문제

# 문제 해설 및 코드 리뷰

package com.core.hello;
import java.util.*;
class Main{
    static int n, m;
    static int s, e;
    static ArrayList<Integer>[] list;
    static int[] arr;
    static boolean[] visit;
    static int answer = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        list = new ArrayList[n + 1];
        arr = new int[n + 1];
        for(int i = 0; i <= n; i++){
            list[i] = new ArrayList<>();
        }
        visit = new boolean[n + 1];
        for(int i = 0; i < m; i++){
            int x = scan.nextInt();
            int y = scan.nextInt();
            list[x].add(y);
            list[y].add(x);
        }

        s = scan.nextInt();
        e = scan.nextInt();
        pro();
        System.out.println(answer);
    }
    static void pro(){
        for(int i = 1; i<= n; i++){
            Collections.sort(list[i]);
        }
        bfs(s,e);
        visit = new boolean[n + 1];
        int last = arr[e];
        while(last > 0){
            visit[last] = true;
            last = arr[last];
        }
        bfs(e,s);
    }
    static void bfs(int x, int y){
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(x, 0));
        visit[x] = true;
        while(!queue.isEmpty()){
            Node now = queue.poll();
            for(int i : list[now.idx]){
                if(!visit[i]){
                    visit[i] = true;
                    arr[i] = now.idx;
                    queue.offer(new Node(i,now.cnt + 1));
                }
                if(i == y){
                    answer += now.cnt + 1;
                    return;
                }
            }
        }
    }
    static class Node{
        int idx;
        int cnt;
        Node(int idx, int cnt){
            this.idx = idx;
            this.cnt = cnt;
        }
    }
}

이 문제는 정점을 도달한 후 방문하지 않은 인덱스로 다시 원점으로 돌아올 수 있게끔 푸는 문제입니다.

따라서 int타입의 arr를 이용하거나 돌아올 때 점을 다시 초기화시켜주지 않으면 큰일나게됩니다.

그러므로 ArrayList<>[]를 이용하여 풀이하도록 합니다.

단순히 arr[x][y] = arr[y][x] = 1로 저장하여 노드를 설정할 수도 있겠으나 이 문제의 경우 arr[x]점에 해당하는 열 값은 y가 해당되는 것을 찾기 위해 굳이 int타입의 arr를 이용했을 때의 for문의 시간 낭비를 줄이고자 list[]를 사용하는 것이니 이해를 꼭 하고 넘어가시길 바랍니다.

풀이를 해보겠습니다.

static int n, m;
static int s, e;
static ArrayList<Integer>[] list;
static int[] arr;
static boolean[] visit;
static int answer = 0;

static 변수로 다음과 같이 선언합니다.

여기서 쓰이는 arr는 방문한 점을 int로 표시하기 위함입니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
list = new ArrayList[n + 1];
arr = new int[n + 1];
for(int i = 0; i <= n; i++){
    list[i] = new ArrayList<>();
}

Scanner를 이용하여 n과 m을 입력받고 list를 ArrayList타입으로 총 n + 1크기만큼 선언합니다.

그리고 list[i]는 모두 ArrayList로 선언하고 visit도 n + 1크기로 선언합니다.

for(int i = 0; i < m; i++){
    int x = scan.nextInt();
    int y = scan.nextInt();
    list[x].add(y);
    list[y].add(x);
}

이후 x와 y를 입력받아 list[x]에는 y를, list[y]에는 x를 삽입합니다.

그리고

s = scan.nextInt();
e = scan.nextInt();
pro();
System.out.println(answer);

s와 e를 입력받고 pro()를 실행합니다.

static void pro(){
    for(int i = 1; i<= n; i++){
        Collections.sort(list[i]);
    }
    bfs(s,e);
    visit = new boolean[n + 1];
    int last = arr[e];
    while(last > 0){
        visit[last] = true;
        last = arr[last];
    }
    bfs(e,s);
}

pro()함수는 입력받은 list들을 사전순으로 정렬하고 시작점부터 정점까지 방문과 정점에서 시작점까지의 방문을 수행할 것입니다.

먼저 오름차순으로 list를 정렬할 땐 Collections.sort(list[i])를 입력합니다.

이 때 각 list[i]에 대해서 총 n번 수행해야 하므로 for문을 이용합니다.

이후 bfs(s,e)를 실행하는데 시작점에서 정점까지의 bfs를 체킹하겠습니다.

static void bfs(int x, int y){
    Queue<Node> queue = new LinkedList<>();
    queue.offer(new Node(x, 0));
    visit[x] = true;
    while(!queue.isEmpty()){
        Node now = queue.poll();
        for(int i : list[now.idx]){
            if(!visit[i]){
                visit[i] = true;
                arr[i] = now.idx;
                queue.offer(new Node(i,now.cnt + 1));
            }
            if(i == y){
                answer += now.cnt + 1;
                return;
            }
        }
    }
}

시작점에서 정점까지 방문할 로직을 처리할 자료구조는 Queue를 이용하도록 합시다.

queue에 점을 삽입하고 visit을 true로 바꾸어주겠습니다.

이후 while문을 써서 queue의 미참조 에러를 방지하고 queue에서 뽑아온 현재 점의 인덱스에 대해서 now라고 지정하겠습니다.

최초의 시행시 now점은 x, 0이 삽입되어 있을 것입니다.

이 때 x는 index, 0은 count를 뜻하는데

static class Node{
    int idx;
    int cnt;
    Node(int idx, int cnt){
        this.idx = idx;
        this.cnt = cnt;
    }
}

Queue의 제네릭구조는 다음과 같이 설정했으니 참고해주세요.

어쨌든 본론으로 돌아가, x , 0을 삽입했으므로 다시 말해 s점부터 y점에 도달할 때까지 탐색을 진행하겠습니다.

그러므로 list[x]에 대한 점들 중 (x와 연결된 여러 개의 점들이 존재할 것입니다) 사전순으로 정렬했으므로 적은 점들부터 차례로 탐색을 진행합니다.

방문하지 않은 visit에 대해 visit은 true로 바꾸어주고 arr[i]에는 현재의 점을 삽입한 후 queue에 i와 now.cnt + 1하여 삽입합니다.

이렇게 되면 최초의 x점에 연결될 사전순으로 앞에 있는 점이 연결될 것입니다.

이 작업을 계속 수행 후 i == y가 되면 answer에 now.cnt + 1을 한 후 return합니다.

visit = new boolean[n + 1];
int last = arr[e];
while(last > 0){
    visit[last] = true;
    last = arr[last];
}
bfs(e,s);

다시 돌아와서 visit을 초기화 하고 last = arr[e]를 넣습니다.

이후 앞 단계에서 정점으로 갈 때의 visit을 모두 true로 바꾼 후 돌아오는 작업도 똑같이 bfs(s,e)를 실행합니다.

돌아올 때에도 마찬가지로 answer에 now.cnt + 1을하여 return하면 도착할 때의 점까지의 거리를 구할 수 있습니다.

감사합니다.