[구름톤 챌린지, Java] 16일차, 연합(BFS)

문제 링크

 

구름LEVEL

---

접근 방법

이 문제에 핵심

1. 바다 위에는 N개의 섬이 존재합니다.

2. 섬을 연결하는 다리는 정방향, 역방향 최대 2개이며, 모든 다리는 단방향입니다.

3. 섬이 연합을 할 때에는 정방향, 역방향 다리가 2개가 존재해야 합니다.

4. a와 b가 연합이고, b와 c가 연합이면 a와 c는 연합입니다.

5. 모든 연합의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 연합이 속하지 않은 각 섬을 BFS를 이용하여 연합을 구성합니다.

 

3. 탐색이 종료되었을 때 연합의 개수를 결과로 출력합니다.

 

 

구현

 

BFS을 진행할 때 3가지 경우가 존재합니다.

 

서로 아무 다리가 놓여지지 않았을 때(연합 X)

 

단방향 다리만 연결 되었을 때(연합 X)

양방향(정, 역) 다리만 연결 되었을 때(연합 O)

 

위 3가지 경우를 고려해서 연합이 성립하면 해당 섬이 어떤 연합에 속해있다는 것을 boolean[]로 저장합니다.

 

BFS을 종료하면 모든 섬은 연합에 속해있습니다.

 

BFS 진행한 횟수 = 연합의 개수

 

 

 

Why??

 

BFS를 진행할 때마다 하나의 연합이 생기기 때문입니다.

 

 

 

예제입력 진행과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 1.

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

 

N : 4

 

M : 6

 

2. 연합이 속하지 않은 각 섬을 BFS를 이용하여 연합을 구성합니다.

 

연합에 속하지 않은 1번 섬 BFS 진행!

 

 

 

 

섬1 : 섬2

▶ 정방향(1 → 2)만 존재합니다. ▶ 연합 X

 

섬1 : 섬3

▶ 정방향(1 → 4), 역방향(4 → 1)만 존재합니다. ▶ 연합 O

 

연합에 속하지 않은 2번 섬 BFS 진행!

 

섬2 : 섬3

▶ 정방향(2 → 3)만 존재합니다. ▶ 연합 X

 

섬2 : 섬4

▶ 정방향(2 → 4)만 존재합니다. ▶ 연합 X

 

연합에 속하지 않은 3번 섬 BFS 진행!

 

 

섬3 : 섬4

▶ 정방향(3 → 4)만 존재합니다. ▶ 연합 X

 

연합에 속한 4번 섬은 BFS 진행 X!

 

3. 탐색이 종료되었을 때 연합의 개수를 결과로 출력합니다.

 

연합1	연합2	연합3
{ 1, 4 }	{ 2 }	{ 3 }

 

연합의 개수 : 3개

 

3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• 연합에 속하지 않은 섬을 기준으로 grouping함수를 실행하여 연합을 맺습니다.
• 모든 연합 맺기가 종료된 뒤 연합의 개수를 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• grouping은 bfs를 통해서 정방향, 역방향으로 연결된 섬끼리 연합을 맺어줍니다.

 

결과코드

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

class Main {
    //다리 정보 저장하는 리스트
    static List<List<Integer>> bridge = 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());
        //다리 리스트 초기화
        for(int i=0;i<=N;i++){
            bridge.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());
            bridge.get(s).add(e);
        }
        //연합 확인 booelan 배열
        boolean[] isGroup = new boolean[N+1];
        //연합 개수
        int result = 0;
        //연합에 속하지 않은 섬 BFS으로 인한 연합 맺기
        for(int i=1;i<=N;i++){
            //이미 연합에 속한 경우
            if(isGroup[i]) {
                continue;
            }
            //연합 맺기 진행
            grouping(i, isGroup);
            //연합 개수 증가
            result++;
        }
        //연합 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 이용해서 조건에 맞게 연합을 맺는 함수
    static void grouping(int start, boolean[] isGroup){
        //BFS에 활용할 Queue
        Queue<Integer> q = new ArrayDeque<>();
        //탐색 시작 섬 Queue 저장
        q.offer(start);
        //시작 섬 연합 적용
        isGroup[start] = true;
        //BFS탐색 진행
        while(!q.isEmpty()){
            int cur = q.poll();
            //연결된 정방향 다리 탐색
            for(int nxt : bridge.get(cur)){
                //연합에 속하지 않고, 역방향 다리를 갖는 경우 : 연합 O
                if(!isGroup[nxt] && bridge.get(nxt).contains(cur)){
                    q.offer(nxt);
                    isGroup[nxt] = true;
                }
            }
        }
    }
}

 

---

느낀 점

 

그래프 탐색 문제를 많이 풀어보았다고 생각하였지만, 정방향/역방향 관련된 문제는 처음 접하게 되었습니다.

 

아직 접해봐야 하는 문제가 더 많다는 것을 깨닫게 되면서 더 열심히 해야겠다고 마음을 먹었습니다.