[구름톤 챌린지, Java] 14일차, 작은 노드(BFS)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. N개의 노드와  M개의 양방향 간선으로 이루어진 그래프가 존재합니다.

2. 양끝이 동일한 간선은 주어지지 않습니다.

3. 플레이어는 K번 노드에 있으며, 한 번 방문한 노드는 다시 방문할 수 없습니다.

4. 플레이어가 간선을 통해 노드를 방문할 때 인접한 가장 작은 노드를 접근합니다.

5. 플레이거가 방문하는 노드의 개수와 마지막으로 방문하는 노드를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 시작 노드 K를 기준으로 조건에 맞는 BFS을 방문하는 노드를 탐색합니다.

 

3. 탐색이 끝났을 때 방문한 노드와 마지막 노드를 결과로 출력합니다.

 

 

구현

 

K번 노드를 시작으로 BFS을 통해서 노드를 방문합니다.

 

 

K = 1

 

 

 

 

K(1번) 노드부터 BFS을 진행합니다.

 

인접한 노드는 { 2, 4 }이기 때문에 더 작은 노드 2번으로 탐색을 진행합니다.

 

현재 노드(2번)에서 인접한 노드는 { 1, 3 }이기 때문에 3번으로 탐색합니다.

※1번 노드는 이미 탐색하였기 때문에 제외됩니다.

 

 

현재 노드 3번에서 인접한 노드는 { 2 }입니다.

 

하지만, 2번 노드는 방문하였기 때문에 재방문이 불가능합니다.

 

결과적으로, 더 이상 방문할 수 있는 노드가 존재하지 않기 때문에 탐색을 종료합니다.

 

방문한 노드의 개수 : 3개

 

마지막 방문 노드 : 3번

 

위와 같이 BFS을 통해서 결과를 도출하였습니다.

 

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 6

M : 6

K : 1

 

 

2. 시작 노드 K를 기준으로 조건에 맞는 BFS을 방문하는 노드를 탐색합니다.

 

K(1)번 노드부터 탐색

 

 

 

 

K(1)번 노드와 인접한 노드는 { 2, 3 }이며, 방문하지 않고 가장 작은 노드는 2번 노드입니다.

 

현재 노드(2번) 탐색 진행

 

 

 

2번 노드와 인접한 노드는 { 1, 3 }이며, 방문하지 않고 가장 작은 노드는 3번 노드입니다.

 

현재 노드(3번) 탐색 진행

 

 

3번 노드와 인접한 노드는 { 1, 2, 4, 5 }이며, 방문하지 않고 가장 작은 노드는 4번 노드입니다.

 

현재 노드(4번) 탐색 진행

 

 

4번 노드와 인접한 노드는 { 3, 6 }이며, 방문하지 않고 가장 작은 노드는 6번 노드입니다.

 

현재 노드(6번) 탐색 진행

 

 

6번 노드와 인접한 노드는 { 3, 6 }이며, 방문하지 않고 가장 작은 노드는 존재하지 않습니다.

 

 

3. 탐색이 끝났을 때 방문한 노드와 마지막 노드를 결과로 출력합니다.

 

 

BFS 방문 순서

 

1 → 2 → 3 → 4 → 6 : 방문 개수 : 5개

 

마지막 방문 노드 : 6번

 

5 6을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• 현재 노드 기준 bfs함수을 통해서 탐색을 진행합니다.
• 방문 노드의 개수와 마지막 방문 노드를 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• bfs함수는 BFS을 통해서 간선이 연결된 노드들을 탐색합니다.

 

결과코드

import java.io.*;
import java.util.*;

class Main {
    //간선 정보 저장 리스트
    static List<List<Integer>> list = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //입력값 저장
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        //간선 리스트 초기화
        for(int i=0;i<=N;i++){
            list.add(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());
            //간선 양방향 저장
            list.get(s).add(e);
            list.get(e).add(s);
        }
        //가장 낮은 번호을 우선순위로 진행하기 때문에 각 간선 오름차순 정렬
        for(int i=0;i<=N;i++){
            Collections.sort(list.get(i));
        }
        //시작노드 K를 기준으로 BFS 탐색
        int[] result = bfs(K, N);
        //방문한 노드 개수 및 마지막 방문 노드 정보 BufferedWriter 저장
        StringBuilder sb = new StringBuilder();
        sb.append(result[0]).append(" ").append(result[1]);
        bw.write(sb.toString());
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 통해 조건에 맞는 노드 탐색하는 함수
    static int[] bfs(int K, int N){
        //result[0] : 방문 노드 개수, result[1] : 마지막 방문 노드
        int[] result = new int[2];
        //방문 여부 확인 배열
        boolean[] visited = new boolean[N+1];
        //BFS에 사용할 Queue
        Queue<Integer> queue = new ArrayDeque<>();
        //초기 위치(K번) 방문 확인 및 Queue설정
        visited[K] = true;
        result[0]++;
        result[1] = K;
        queue.offer(K);
        //BFS 탐색 진행
        while(!queue.isEmpty()){
            int cur = queue.poll();
            //연결된 노드 중 가장 낮은 번호 노드 탐색
            for(int nxt : list.get(cur)){
                //방문하지 않았던 노드일 때
                if(!visited[nxt]){
                    visited[nxt] =true;
                    queue.offer(nxt);
                    result[0]++;
                    result[1] = nxt;
                    break;
                }
            }
        }
        //결과값 반환
        return result;
    }
}

 

---

느낀 점

 

그래프 문제를 많이 풀어본 경험이 있었기 때문에 문제를 풀 때 큰 어려움은 없었습니다.

 

그래프에 대한 개념을 확실히 잡고 있으니까 문제를 푸는 것에 거부감이 없어서

 

개념에 대한 확실한 이해가 중요하다는 것을 깨닫게 되었습니다.