구름톤 챌린지 4주 Day1 - 연합

연합 (Java)

 

1. 입력으로 섬의 수 N과 다리의 수 M을 받는다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int N, M;
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt(); // 섬의 수
        M = scanner.nextInt(); // 다리의 수

2. graph 배열을 초기화하고, graph[s][e] 값이 1이면 섬 s에서 섬 e로 이동 가능한 단방향 다리가 있다는 것을 나타낸다.

        int[][] graph = new int[N + 1][N + 1]; // 섬과 다리 연결 정보를 나타내는 그래프
        for (int i = 0; i < M; i++) {
            int s = scanner.nextInt(); // 다리의 시작 섬
            int e = scanner.nextInt(); // 다리의 끝 섬

            graph[s][e] = 1; // 섬 s에서 섬 e로 이동 가능한 다리가 있다는 표시 (단방향)
        }

3. visited 배열은 섬들의 연합 정보를 저장한다.

초기에는 0으로 초기화되며, 연합이 형성될 때마다 증가된다.

        int[] visited = new int[N + 1]; // 섬의 연합 정보를 저장하는 배열
        int count = 1; // 현재까지 발견한 연합의 수, 1부터 시작

4.모든 섬을 순회하면서 아직 연합에 속하지 않은 섬을 찾는다.

이때 BFS를 사용하여 연합을 찾는다.

        for (int i = 1; i <= N; i++) {
            if (visited[i] == 0) { // 아직 연합에 속하지 않은 섬을 찾으면
                Queue<Integer> q = new LinkedList<>();
                q.add(i); // 해당 섬을 큐에 추가하여 BFS 시작

                while (!q.isEmpty()) { // BFS로 연합 찾기
                    int currentNode = q.poll(); // 큐에서 현재 섬을 가져옴
                    visited[currentNode] = count; // 현재 섬이 count 번 연합에 속함을 표시

                    for (int nextNode = 1; nextNode <= N; nextNode++) {
                        if (graph[currentNode][nextNode] == 1 && graph[nextNode][currentNode] == 1
                                && visited[nextNode] == 0) {

 

5. BFS를 통해 연합을 찾을 때, 현재 섬과 다른 섬 사이에 양방향 다리가 있고 아직 연합에 속하지 않은 경우,

그 다른 섬을 큐에 추가하여 탐색을 진행한다.

                    for (int nextNode = 1; nextNode <= N; nextNode++) {
                        if (graph[currentNode][nextNode] == 1 && graph[nextNode][currentNode] == 1
                                && visited[nextNode] == 0) {
                            // 현재 섬과 다른 섬 사이에 양방향 다리가 있고, 아직 연합에 속하지 않은 경우
                            q.add(nextNode); // 다음 섬을 큐에 추가하여 탐색 계속
                        }
                    }
                }

 

6. BFS가 종료되면 연합 번호를 증가시키고, 이 과정을 모든 섬에 대해 반복한다.

                count++; // 연합 번호 증가
            }
        }

 

7. 마지막으로, 총 연합의 수를 출력할 때는 count - 1을 출력합니다. 이는 초기값이 1로 설정되어 있으므로 하나를 빼주어야 실제 연합의 수가 된다.

        System.out.println(count - 1); // 총 연합의 수 출력 (1을 빼줘야 함)
    }
}

 

큐가 무엇인지 궁금해서 조사를 해보았는데,

정보처리기사 시험을 볼 때 배웠던 선입선출 큐를 말하는 것이었다. 

 

자바에서 큐를 사용하는 방법이 따로 있어서 조사해 보았다. 

 

자바에서 큐를 사용하는 방법

자바 큐란? - 큐 자바 구현 (QUEUE)

 

[JAVA] Queue(큐) 사용법 (add vs offer / remove vs poll / element vs peek)

 

[자료구조 Java] 큐(Queue) 개념 정리 + 자바로 구현하기

 

문제 풀이

분석

연합 문제는 그래프에서 조건에 맞는 연합을 찾고, 연합의 개수를 세는 문제입니다. BFS의 개념을 잘 이해하고 있다면, 어렵지 않게 문제를 해결할 수 있습니다.

문제 풀이

문제를 해결하기 위해서는 DFS와 BFS 어떤 방법으로 해결할 수 있지만, 결과적으로 모든 섬을 방문해야 하기 때문에 BFS로 문제를 해결할 수 있습니다.

연합의 조건은 다음과 같습니다.

• A섬과 B섬이 있을 때, 서로 이동할 수 있으면 연합이 될 수 있다.
• 연합 안에서 어떤 섬에서 출발해도, 연합의 모든 섬에 방문할 수 있어야 한다.
• 모든 섬은 하나의 연합에 속해있다.

위의 조건으로 만들어진 연합에 어떤 섬이 포함되어 있는지 알 수 있다면, 가장 마지막에 만들어진 연합의 번호가 곧 연합의 개수가 됩니다.

그래프 구현

그래프 기초 문제에서 자바로 그래프를 구현하는 방법을 배웠습니다. 자바에서 그래프는 HaspMap 을 이용해서 구현합니다.

• graph.putIfAbsent(s, new ArrayList<>());
• 만약에 graph에 s 라는 키가 없으면, graph[s] 에 new ArrayList<>() 를 할당합니다. 그래프 선언할 때 유용합니다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N, M;
		Map<Integer, List<Integer>> graph = new HashMap<>();
		String[] firstLine = scanner.nextLine().split(" ");
		N = scanner.nextInt();
    M = scanner.nextInt();
		for (int i = 0; i < M; i++) {
			String[] edge = scanner.nextLine().split(" ");
			int s = Integer.parseInt(edge[0]);
			int e = Integer.parseInt(edge[1]);
			graph.putIfAbsent(s, new ArrayList<>());
			graph.get(s).add(e);
		}
		System.out.println(graph);
	}
}

연합의 개수

연합의 개수를 세기 위해서 visited 변수를 활용할 수 있습니다. visited 는 섬의 방문 여부와 함께 어떤 연합에 속해져 있는지 확인할 수 있습니다. 아래와 같이 연합을 관리합니다.

• int[] visited = new int[N + 1]; visited 변수를 선언합니다.
  1. visited[Node] 의 값이 0 이면, 그 섬은 어떤 연합에도 포함되지 않은 섬이다.
  2. 연합에 속하지 않는 섬에서, 새로운 연합을 만들었을 때 이를 $i$번 연합이라고 한다.
  3. $i$번 연합에 속한 섬들을 visited[Node] = i 로 갱신한다.
• count 는 소속 연합의 번호를 관리합니다.
• if (graph.get(nextNode).contains(currentNode) && visited[nextNode] == 0)
• graph의 한 노드에는 ArrayList 가 포함되어 있습니다. 내가 방문할 노드에 currentNode가 포함되어 있는지 확인해야 합니다.

// count = 연합의 번호
// visited = 방문 기록 & 연합 기록 확인
int[] visited = new int[N + 1];
int count = 1;

for (int i = 1; i <= N; i++) {
	if (visited[i] == 0) {
		Queue<Integer> q = new LinkedList<>();
		q.add(i);
		// 탐색 후보가 비워질 때 까지 탐색합니다.
		while (!q.isEmpty()) {
			// BFS로 구현합니다.
			int currentNode = q.poll();
			// 현재 방문한 노드를 연합의 번호를 할당합니다.
			visited[currentNode] = count;
			// Java의 경우에는 graph에 탐색하려는 key 값이 있는지 확인해야합니다.
			if (graph.containsKey(currentNode)) {
				for (int nextNode : graph.get(currentNode)) {
					if (graph.containsKey(nextNode)){
						//nextNode 에서 current Node로 올 수 있는지도 확인 && 연합 소속 여부 확인.
						if (graph.get(nextNode).contains(currentNode) && visited[nextNode] == 0){
							q.add(nextNode);
						}
					}
				}
			}
		}
		// 한 노드에서 갈 수 있는 모든 연합을 구하면, 연합의 번호를 올립니다.
		count++;
	}
}

위와 같은 논리로 작성하게 되면, Timeout이 발생합니다. 논리적으로는 틀리지 않았습니다. 다만 조금 더 최적화 를 해야합니다.

Timeout 해결하기

graph.get(nextNode).contains(currentNode) 는 graph[nextNode] 에서 currentNode 의 존재 여부를 찾는 시간은 항상 graph.get(nextNode) 의 길이만큼 시간이 걸립니다. 이 탐색 시간이 오래 걸리기 때문에 몇몇 케이스에 Timeout 이 발생합니다.

그래프의 개념을 설명했을 때, 인접 행렬과 인접 리스트의 개념을 배웠습니다. 이 둘의 차이는 a, b 두 개의 선의 간선의 존재 여부를 찾을 때 걸리는 시간입니다. 그리고 이를 해결해주기 위해서, 인접 행렬 리스트를 선언하여 해결할 수 있습니다.

바로 이 시간이 오래 걸리기 때문에 몇 개의 저격 케이스에서 오답이 발생하고 있는 겁니다.

이 시간을 줄이는 방법은 상당히 간단합니다. 인접 행렬 그래프도 같이 선언하면 됩니다. 처음 그래프의 간선을 만들어 줄 때, check 행렬을 만들고, check[s][e] 를 1 로 바꿔줄 겁니다.

중요한 부분은 nextNode 에서 currentNode 로 오는 간선의 존재 여부를 파악할 때, check[nextNode][currentNode] 가 1인지 확인하는 코드를 추가하면, 간선의 존재 여부를 확인하는 시간을 획기적으로 줄일 수 있습니다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		..code
		int[][] check = new int[N + 1][N + 1];
		for (int i = 0; i < M; i++) {
			int s = scanner.nextInt();
			int e = scanner.nextInt();
			graph.putIfAbsent(s, new ArrayList<>());
			graph.get(s).add(e);
			// s -> e 로 가는 간선의 존재를 갱신
			check[s][e] = 1;
		}
		
		int[] visited = new int[N + 1];
		int count = 1;

		for (int i = 1; i <= N; i++) {
			if (visited[i] == 0) {
				Queue<Integer> q = new LinkedList<>();
				q.add(i);
				while (!q.isEmpty()) {
					int currentNode = q.poll();
					visited[currentNode] = count;
					if (graph.containsKey(currentNode)) {
						for (int nextNode : graph.get(currentNode)) {
							if (graph.containsKey(nextNode)){
								// check 매트릭스에서 간선의 존재 여부를 확인합니다.
								if (check[nextNode][currentNode] == 1 && visited[nextNode] == 0){
									q.add(nextNode);
								}
							}
						}
					}
				}
				count++;
			}
		}
		System.out.println(count - 1);
	}
}

Timeout code

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int N, M;
		Map<Integer, List<Integer>> graph = new HashMap<>();
		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		M = scanner.nextInt();
		for (int i = 0; i < M; i++) {
			int s = scanner.nextInt();
			int e = scanner.nextInt();
			graph.putIfAbsent(s, new ArrayList<>());
			graph.get(s).add(e);
		}
		int[] visited = new int[N + 1];
		int count = 1;

		for (int i = 1; i <= N; i++) {
			if (visited[i] == 0) {
				Queue<Integer> q = new LinkedList<>();
				q.add(i);
				while (!q.isEmpty()) {
					int currentNode = q.poll();
					visited[currentNode] = count;
					if (graph.containsKey(currentNode)) {
						for (int nextNode : graph.get(currentNode)) {
							if (graph.containsKey(nextNode)){
								if (graph.get(nextNode).contains(currentNode) && visited[nextNode] == 0){
									q.add(nextNode);
								}
							}
						}
					}
				}
				count++;
			}
		}
		System.out.println(count - 1);
	}
}

 

정해코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int N, M;
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();

        int[][] graph = new int[N + 1][N + 1];
        for (int i = 0; i < M; i++) {
            int s = scanner.nextInt();
            int e = scanner.nextInt();

            graph[s][e] = 1;
        }

        int[] visited = new int[N + 1];
        int count = 1;

        for (int i = 1; i <= N; i++) {
            if (visited[i] == 0) {
                Queue<Integer> q = new LinkedList<>();
                q.add(i);

                while (!q.isEmpty()) {
                    int currentNode = q.poll();
                    visited[currentNode] = count;

                    for (int nextNode = 1; nextNode <= N; nextNode++) {
                        if (graph[currentNode][nextNode] == 1 &&
                            graph[nextNode][currentNode] == 1 &&
                            visited[nextNode] == 0) {
                            q.add(nextNode);
                        }
                    }
                }
                count++;
            }
        }

        System.out.println(count - 1);
    }
}

섬이 연합에 포함 되었음을 고려하지 않고도 해결할 수 있습니다. 해설에서 이와 관련된 부분을 추가로 서술한 이유는 visited 변수를 활용하여 방문 지점 이외에도 다양한 정보를 관리할 수 있다는 점을 전달하기 위해서 추가한 내용입니다.

만약에 이 문제가 연합 중에서 가장 크기가 큰 연합을 찾으라는 문제였다면, visited 변수를 통해서 해결이 가능하죠. 아래는 visited 변수를 방문 여부만 확인하고 해결할 수 있는 코드입니다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		int N, M;
		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		M = scanner.nextInt();
		Map<Integer, List<Integer>> graph = new HashMap<>();
		int[][] check = new int[N + 1][N + 1];
		for (int i = 0; i < M; i++) {
			int s = scanner.nextInt();
			int e = scanner.nextInt();
			graph.putIfAbsent(s, new ArrayList<>());
			graph.get(s).add(e);
			// s -> e 로 가는 간선의 존재를 갱신
			check[s][e] = 1;
		}
		
		boolean[] visited = new boolean[N + 1];
		int count = 1;

		for (int i = 1; i <= N; i++) {
			if (visited[i] == false) {
				Queue<Integer> q = new LinkedList<>();
				q.add(i);
				while (!q.isEmpty()) {
					int currentNode = q.poll();
					visited[currentNode] = true;
					if (graph.containsKey(currentNode)) {
						for (int nextNode : graph.get(currentNode)) {
							if (graph.containsKey(nextNode)){
								// check 매트릭스에서 간선의 존재 여부를 확인합니다.
								if (check[nextNode][currentNode] == 1 && visited[nextNode] == false){
									q.add(nextNode);
								}
							}
						}
					}
				}
				count++;
			}
		}
		System.out.println(count - 1);
	}
}