[Baekjoon] 백준 10775 공항 (G2^ / 서로소) - Java

링크

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

10775번: 공항

 

 

 

문제 해석

- 문제 해석

첫 번째 줄 : N # 게이트의 수
두 번째 줄 : M # 비행기수
세 번째 줄 : a # 1~a까지 비행기가 들어올 수 있음
네 번째 줄 : b # 1~b까지 비행기가 들어올 수 있음

한 대라도 들어올 수 없다면 폐쇄

 

 

- 입력
4 # 4개의 게이트
6 # 6대의 비행기
2 # 2번 게이트에 넣음
2 # 1번 게이트에 넣음
3 # 3번 게이트에 넣음
3 # 1~3게이트가 모두 차 있으므로 사용할 수 없음
4
4

 

 

코드

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

public class Main {
	static int[] parents;

	// 공항을 서로소로 관리
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int answer = 0;

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 게이트 수
		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken()); // 비행기 수
		parents = new int[N + 1];

		// make-set
		for (int i = 1; i <= N; i++) {
			parents[i] = i;
		}

		// union
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int air = Integer.parseInt(st.nextToken());

			int ablePort = find(air);

			if (ablePort == 0) {
				break;
			}
			answer++;

			union(ablePort, ablePort - 1);
		}
		
		System.out.println(answer);

	}

	private static int find(int air) {
		if (parents[air] == air) {
			return air;
		} else {
			return parents[air] = find(parents[air]);
		}
	}

	private static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		
		parents[pa] = pb;
		
	}

}

 

 

 

코드 해석

그리디하게 배열로 풀게 되면 시간 초과가 납니다.

 

서로소로 포트 정보를 관리하며, 서로소로 접근하였을 때 0이 나오면(비행장이 사용 불가능하면) 종료되도록 구현하였습니다.

 

먼저 자신의 번호와 동일한 포트가 사용 가능한지 서로소를 확인을 합니다.

 

확인한 포트가 0이라면 그대로 종료를 진행하고, 결과 값을 더한 후 다른 사용 가능한 포트를 찾아서 바꿔줘야 합니다.

 

따라서 현재 사용한 포트와 해당 포트 번호보다 1작은 포트를 union 작업을 수행하여, 현재 포트를 1작은 포트에 연결된 포트(대표자)로 변경합니다.

 

끝(포트1)까지 사용이 되었다면 결국 포트0번으로 연결이 되고, find를 통해 포트 정보를 가져왔을 때 0이 나온다면 앞서 언급하였듯이 비행기 착륙을 종료합니다.

 

 

 

 

발생한 문제 & 해결 방안

기본 서로소 문제는 쉽게 풀었지만 공항과 같이 조금 응용되는 문제에서는 힘들었다.

union은 서로의 집합 중 대표를 찾아서 하나의 대표를 바라보는 집합으로 바꾸는 작업이다!

<- 기본 개념 잊지 않기!!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice