BOJ - 13463 ) Brexit

개발자가될수있을까? 2022. 1. 19. 21:27

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

13463번: Brexit

The input starts with one line containing four space separated integers C, P, X, and L. These denote the total number of countries (2 ≤ C ≤ 200 000), the number of trading partnerships (1 ≤ P ≤ 300 000), the number of your home country (1 ≤ X

www.acmicpc.net

여러개의 행성이 존재하는데, 한 행성이 union을 탈출하면서 해당 행성과 연결되어있는

행성들의 간선개수를 한개씩 줄여준다. 만약 줄여주는 과정에서, 최초로 연결된 간선의 개수의 절반보다

적어진다면, 해당 행성도 탈출한다. 이때 x 인 내가 탈출대상인지를 물어보는 문제이다.

위상정렬으로도 풀수있을것같은데.. 일단은 BFS를 돌면서 간선개수를 줄여주는 식으로 진행하였다.

package algorithm_2022;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ_13463 {

	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int c = Integer.parseInt(st.nextToken());
		int p = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());
		ArrayList<Integer> al[] = new ArrayList[c+1];
		for(int i=1;i<=c;i++) {al[i] = new ArrayList<>();}
		for(int i=0;i<p;i++) {
			st= new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			al[e].add(s); al[s].add(e);
		}
		int line[] = new int[c+1];
		int count[] = new int[c+1];
		boolean leave[] = new  boolean[c+1];
		for(int i=1;i<=c;i++) {
			line[i] = al[i].size();
		} // count of connected lines
		
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		dq.add(l);
		leave[l] = true;
		while(!dq.isEmpty()) {
			int now = dq.poll();
			int size = al[now].size();
			for(int i=0;i<size;i++) {
				int next = al[now].get(i);
				count[next]++;
				if(2*count[next] >=line[next] && !leave[next]) {
					dq.add(next);
					leave[next] = true;
				}
			}
		}
		System.out.println(leave[x] ? "leave":"stay");
	}
}