Baekjoon 14594 동방 프로젝트 (Small) JAVA

14594번: 동방 프로젝트 (Small)

문제

동아리방이 가지고 싶었던 병찬이는 LINK 사업단에 문의하여 N개의 방 중의 하나를 얻을 기회를 얻었다. 일자로 되어있는 건물에 N개의 방은 일직선상에 존재하며, 각 방에는 번호가 매겨져 있다. 맨 왼쪽 방의 번호는 1번이며, 순서대로 증가하여 맨 오른쪽 방의 번호가 N번이다. 각 방 사이에는 방을 구분하는 벽이 존재한다.

물론 병찬이 외에도 많은 사람이 동아리방을 원한다. 다행히 방은 충분했기에 병찬이는 안심하고 있었지만…

그때였다.

빅-종빈빌런이 나타나 건물 벽을 허물기 시작한 것이다! 빅-종빈빌런은 다음과 같은 규칙으로 벽을 무너뜨린다.

• x < y 를 만족하는 두 방에 대해서 x번 방부터 y번 방 사이에 있는 모든 벽을 허문다.
• 두 방 사이의 벽이 허물어지면 두 방은 하나의 방으로 합쳐진다.
• 이미 허물어진 벽이 존재한다면 무시하고 다음 벽을 허문다.
• 빅-종빈빌런은 건물이 무너지는 걸 원치 않기 때문에, 1번 방의 왼쪽 벽과 N번 방의 오른쪽 벽(즉, 바깥과 연결된 벽)은 허물지 않는다.

동아리 방의 개수가 점점 줄어들자 병찬이는 초조해졌다. 이에 병찬이는 동아리방을 얻을 수 있는지에 대한 확률을 계산하기 위해 남는 동아리방의 수를 구하고 싶어 한다. 병찬이를 위해 빅-종빈빌런의 행동 횟수 M과 동방의 개수 N이 주어졌을 때, 남은 동아리방의 수를 구해주자.

 

조건

[입력]

첫 번째 줄에는 동아리방의 개수를 나타내는 양의 정수 N(2 ≤ N ≤ 100) 이 주어진다. 두 번째 줄에는 빅-종빈빌런의 행동 횟수를 나타내는 음이 아닌 정수 M(0 ≤ M ≤ 100) 이 주어진다. 세 번째 줄부터 M개의 줄에 걸쳐 빅-종빈빌런의 행동이 양의 정수 x, y(1 ≤ x < y ≤ N) 로 주어진다. 여기서 행동이란 x번 방부터 y번 방 사이의 벽을 무너뜨리는 것을 의미한다.

빅-종빈빌런은 매우 허당이기 때문에 동일한 행동을 여러 번 할 수 있음에 유의하라.

 

[출력]

빅-종빈빌런의 모든 행동이 끝난 후 남아있는 동방의 개수를 한 줄에 출력한다.

 

풀이

해당 문제는 숫자 두 개가 주어졌을 때 두 개를 모두 연결하고 최종적으로 남아있는 동방의 개수를 출력하는 문제다.

해당 문제를 보고 union find가 떠올랐고 비슷하게 해결하였다. 로직은 아래와 같다.

 

1. 입력 처리를 한다.

2. 배열을 만들고 자기 자신을 가리키도록 초기화한다.

3. 두 수를 입력받고 해당 숫자의 범위만큼 반복한다.

    1. 만약 배열이 자기 자신을 가리키지 않으면 저장된 값을 따로 저장한다.

    2. 저장된 값이 있으면 해당 값으로 배열 값을 변경한다.

    3. 저장된 값이 없으면 반복문을 시작하는 값으로 저장한다.

4. 배열을 탐색하면서 배열 인덱스와 값이 같은 경우 카운트를 증가시킨다.

5. 카운트를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] map = new int[N+1];
		for (int i = 1; i <= N; i++) { // 배열이 자기 자신을 가리키도록 한다.
			map[i] = i;
		}
		int M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int temp = 0;
			for (int j = a; j <= b; j++) { // 입력된 두숫자만큼 반복을 하면서 배열을 갱신해준다.
				if(map[j] != j) // 만약 배열이 자기 자신을 가리키지 않는다면 이미 연결된 상태 해당값을 저장한다.
					temp = map[j];
				if(temp != 0) // 저장된 값이 있으면 해당값으로 연결되도록 한다. 
					map[j] = temp;
				else // 시작값으로 연결한다.
					map[j] = a;
			}
		}
		int ans = 0;
		for (int i = 1; i <= N; i++) { // 배열을 탐색하면서 배열 인덱스와 배열 값이 같으면 하나의 그룹이므로 수를 증가시킨다.
			if(map[i] == i)
				ans++;
		}
		System.out.println(ans);
	}
}

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드