da9dac

문제

접근 방식

내리 칭찬이 있어서 부하는 상사가 받은 칭찬 + 상사한테 받을 칭찬을 받을 수 있다.

트리에서 상사는 부모고 부하는 자식이니 루트부터 방문을 하면서

부하에게 현재까지 본인이 받은 칭찬을 넘겨주기만 하면 된다.

조심해야할게 한 명의 부하가 여러번 칭찬을 받을 수 있어서

입력을 받을 때

부하 번호 = 부하가 직속 상사로부터 받은 칭찬 이 아니라

부하 번호 += 부하가 직속 상사로부터 받은 칭찬 이 되어야 한다.

풀이

public class Main {

	private static final ArrayList<ArrayList<Integer>> near = new ArrayList<>();
	private static int[] compliments;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int p;
		compliments = new int[n + 1];

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		st = new StringTokenizer(br.readLine());

		for (int i = 1; i <= n; i++) {
			p = Integer.parseInt(st.nextToken());
			if (p == -1) continue;

			near.get(p).add(i);
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			compliments[Integer.parseInt(st.nextToken())] += Integer.parseInt(st.nextToken());
		}

		dfs(1);

		for (int i = 1; i <= n; i++) {
			sb.append(compliments[i]).append(" ");
		}

		System.out.println(sb);
	}

	private static void dfs(int cur) {
		for (int next : near.get(cur)) {
			compliments[next] += compliments[cur];
			dfs(next);
		}
	}
}

문제

접근 방식

분리 집합과 유니온 파인드에 대해서 아직 배우지 않아

기존에 풀었던 4803번 문제와 비슷하게 풀면 풀 수 있겠다 생각이 들어

무작정 시도해봤는데 어찌저찌 풀었다.

우선 이번 문제는 그래프가 주어졌을 때

간선을 지우거나 추가하여 하나의 트리로 만들기 위한

총 횟수를 구해야 한다.

간단하게 생각하면

한 정점에서 방문할 수 있는 모든 정점을 방문했을 때

사이클이 존재하지 않는다면 이미 하나의 트리니

기존의 트리와 합치기만 하면 될 것이고

그렇지 않다면 간선을 제거해주고 합쳐주면 된다.

사이클이 존재하는 경우에 몇 개의 간선을 제거해야 하는지는

트리의 규칙을 생각해보면 쉬운데

정점 N개의 트리는 N-1개의 간선을 가지고 있으니

현재까지 발견한 간선의 수 - (N - 1) = 삭제해야 할 간선의 수

라는 것을 알 수 있다.

발그림으로나마 더 쉽게 설명하자면

위와 같이 그래프가 주어졌을 때,

1-2-3은 이미 트리니 그대로 두고

4-5-6-7은 간선의 개수가 N-1보다 하나 더 많으니

간선을 하나 잘라주고

8-9-10-11도 이미 트리니 그대로 두면 된다.

이제 세 트리를 위와 같이 서로 이어주면 되는데

이 경우도 마찬가지로, 각각의 트리를 정점이라 생각했을 때 

N-1개 만큼 간선을 추가해주면 된다.

풀이

public class Main {

	private static int node, edge;
	private static boolean[] isVisited;
	private static final ArrayList<ArrayList<Integer>> near = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int x, y;
		int cut = 0;
		int tree = 0;

		isVisited = new boolean[n + 1];

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());

			near.get(x).add(y);
			near.get(y).add(x);
		}

		for (int i = 1; i <= n; i++) {
			if (isVisited[i]) continue;
			tree++;
			node = edge = 0;
			dfs(i);
			if (edge != (node - 1) * 2) {
				cut += (edge - ((node - 1) * 2))/2;
			}
		}

		System.out.println(cut + tree - 1);
	}

	private static void dfs(int cur) {
		isVisited[cur] = true;
		node++;

		for (int next : near.get(cur)) {
			edge++;
			if (isVisited[next]) continue;
			dfs(next);
		}
	}
}

문제

접근 방식

이전까지의 트리 문제에서는 각 노드 간의 거리가 1이였다면

이번 문제에서는 노드 간 거리가 서로 다르게 주어진다.

그래서 인접 리스트를 만들 때

기존에는 각 각선의 양끝 정점에 대해서만 넣어줬다면

이번에는 정점 간의 거리도 넣어준 후에 탐색만 해주면 된다.

풀이

public class Main {

	private static int start, end, result;
	private static boolean[] isVisited;
	private static final ArrayList<ArrayList<Pair>> near = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int x, y, d;

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		for (int i = 1; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());

			near.get(x).add(new Pair(y, d));
			near.get(y).add(new Pair(x, d));
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			isVisited = new boolean[n + 1];

			dfs(start, 0);
			sb.append(result).append("\n");
		}

		System.out.println(sb);
	}

	private static void dfs(int cur, int move) {
		isVisited[cur] = true;

		for (Pair pair : near.get(cur)) {
			if (isVisited[pair.node]) continue;
			if (pair.node == end) {
				result = move + pair.dist;
				return;
			}
			dfs(pair.node, move + pair.dist);
		}
	}

	private static class Pair {
		int node;
		int dist;

		public Pair(int node, int dist) {
			this.node = node;
			this.dist = dist;
		}
	}
}

문제

접근 방식

정점이 N개이고 루트가 R인 올바른 트리에 대한 간선이 주어졌을 때

정점이 U인 경우에는 몇 개의 정점을 방문할 수 있는지를 알아내면 된다.

예를 들어 위와 같은 트리가 있을 때를 생각해보면

루트인 5번 정점부터 방문하면 당연히 모든 정점인

9개의 정점을 다 방문할 수 있다.

하지만 4번 정점부터 방문한다면 위와 같이 4개의 정점만 방문할 것이고

8번 정점부터 방문한다면 8번 하나만 방문할 수 있다.

이제 특정 정점에 포함된 정점의 개수가 몇 개인지를 알아내면 되는데

이는 트리의 성질을 이용하면 쉽게 계산할 수 있다.

위의 트리를 다시 살펴보면

정점 3의 경우는 자기 자신을 포함한 자식 노드의 정점 수의 합인 3이고

정점 4의 경우도 마찬가지로 자기 자신을 포함한 자식 노드인 3번 노드의

정점 수의 합인 4가 되고, 5번 정점도 마찬가지로 자기 자신 + 4번 + 6번이 된다.

즉, 탐색하면서 부모 노드에 자식 노드들을 더해주면 각 노드에 포함된

모든 정점의 개수를 알 수 있고, 쿼리마다 탐색을 하지 않아도

한 번의 탐색으로 처리할 수 있다.

풀이

public class Main {

	private static final ArrayList<ArrayList<Integer>> near = new ArrayList<>();
	private static int[] counts;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		int x, y;

		counts = new int[n + 1];

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		for (int i = 1; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());

			near.get(x).add(y);
			near.get(y).add(x);
		}

		travel(r);

		while (q-- > 0) {
			sb.append(counts[Integer.parseInt(br.readLine())]).append("\n");
		}

		System.out.println(sb);
	}

	private static void travel(int cur) {
		counts[cur] = 1;

		for (int next : near.get(cur)) {
			if (counts[next] != 0) continue;
			travel(next);
			counts[cur] += counts[next];
		}
	}
}

문제

접근 방식

그래프가 주어졌을 때 해당 그래프에 트리가 몇 개 존재하는지를 구하는 문제다.

즉, 하나의 정점에서 출발하여 갈 수 있는 모든 정점까지 갔을 때

사이클이 존재하지 않으면 하나의 트리라고 볼 수 있고

이렇게 탐색을 했을 때 방문한 정점이 n개, 간선이 n-1개라면

트리라는 것을 알 수 있다.

무방향 그래프에서 트리를 찾는 것이기 때문에 (n - 1) * 2개의 간선이

있는지 확인하여 맞다면 트리의 개수를 1씩 증가시켜주면 된다.

정점을 처음 방문할 때마다 정점의 개수를 카운팅 해주고

해당 정점에 있는 모든 간선을 확인할 때마다 간선의 개수를 카운팅 하고

아직 방문하지 않은 정점인 경우에만 방문해준다.

한 정점에서의 탐색이 모두 끝났다면

현재까지 기록된 정점과 간선의 개수가

트리의 기준에 만족하는지 확인해주면 된다.

풀이

public class Main {

	private static int cnt, node, edge;
	private static ArrayList<ArrayList<Integer>> near;
	private static boolean[] isVisited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int c = 1, n, m, x, y;

		while (true) {
			st = new StringTokenizer(br.readLine());

			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());

			if (n + m == 0) break;

			cnt = 0;
			near = new ArrayList<>();
			isVisited = new boolean[n + 1];

			for (int i = 0; i <= n; i++) {
				near.add(new ArrayList<>());
			}

			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());

				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());

				near.get(x).add(y);
				near.get(y).add(x);
			}

			for (int i = 1; i <= n; i++) {
				if (isVisited[i]) continue;
				node = 0;
				edge = 0;
				dfs(i);
				if (edge == (node - 1) * 2) cnt++;
			}

			sb.append("Case ").append(c++).append(": ");

			if (cnt == 0) sb.append("No trees.");
			else if (cnt == 1) sb.append("There is one tree.");
			else sb.append("A forest of ").append(cnt).append(" trees.");

			sb.append("\n");
		}

		System.out.println(sb);
	}

	private static void dfs(int cur) {
		isVisited[cur] = true;
		node++;

		for (int next : near.get(cur)) {
			edge++;
			if (isVisited[next]) continue;
			dfs(next);
		}
	}
}

문제

접근 방식

그래프에서의 BFS/DFS와 조금만 다르게 코드를 짜면 트리를 순회할 수 있는

BFS/DFS 코드를 만들 수 있다.

기존에 그래프에서는 이전에 방문한 정점인지 확인하기 위해

불리언이나 정수형 배열을 통해 방문 여부를 기록해두었다면

트리는 방문 여부를 확인하는 것이 아니라 부모가 기록 되었는지로

방문 여부를 확인할 수 있다.

기존 BFS/DFS 코드와 마찬가지로 구성은 같지만

다음에 방문할 자식 노드에 부모가 누구인지만 기록해주면 된다.

BFS와 DFS 방식 모두 구현해보았는데 그래프 때도 느꼈지만

재귀 방식인 DFS가 코드가 뭔가 깔끔해서 보기가 좋다.

풀이

public class Main {

	private static int n;
	private static int[] p;
	private static final ArrayList<ArrayList<Integer>> nearList = new ArrayList<>();
	private static StringTokenizer st;
	private static final StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		input();
		bfs();
		dfs(1, 0);
		append();
		System.out.println(sb);
	}

	private static void bfs() {
		p = new int[n + 1];

		Queue<Integer> q = new ArrayDeque<>();
		q.offer(1);

		while (!q.isEmpty()) {
			int cur = q.poll();

			for (int next : nearList.get(cur)) {
				if (p[cur] == next) continue;
				q.offer(next);
				p[next] = cur;
			}
		}

		sb.append("BFS").append("\n");

		append();

		sb.append("\n");
		sb.append("DFS").append("\n");
		p = new int[n + 1];
	}

	private static void dfs(int cur, int parent) {
		p[cur] = parent;

		for (int next : nearList.get(cur)) {
			if (p[cur] == next) continue;
			dfs(next, cur);
		}
	}

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		int x, y;

		for (int i = 0; i <= n; i++) {
			nearList.add(new ArrayList<>());
		}

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());

			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());

			nearList.get(x).add(y);
			nearList.get(y).add(x);
		}
	}

	private static void append() {
		for (int i = 2; i <= n; i++) {
			sb.append(p[i]).append("\n");
		}
	}
}

문제

접근 방식

입력이 복잡하게 주어져서 이걸 어떻게 간선으로 표현할지 난감했는데

결국 진실을 아는 사람들과 연결된지만 확인하여

진실을 아는 사람, 그 사람들과 만난 적 있는 사람들이 참여한 파티라면

전체 파티 수에서 1씩 빼주면 된다.

우선 입력을 받을 때, 같은 파티에 참여한 사람들끼리 서로 인접 그래프에

동일하게 추가해준 후에, 진실을 아는 사람들만 시작 정점으로 하여

DFS로 탐색을 해주면서 방문한 모든 정점들을 참으로 바꿔주면

진실을 아는 사람과 만난 사람들이 누군지까지 알 수 있다.

그 후에 파티 참가자들을 확인하면서 진실을 아는지 확인해주면 된다.

풀이

public class Main {

	private static ArrayList<ArrayList<Integer>> near = new ArrayList<>();
	private static boolean[] isTrue;
	private static boolean[] isUsed;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int s;
		int[] members;
		isTrue = new boolean[n + 1];
		isUsed = new boolean[n + 1];

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		st = new StringTokenizer(br.readLine());

		int tr = Integer.parseInt(st.nextToken());
		int[] trs = new int[tr];
		ArrayList<int[]> parties = new ArrayList<>();

		for (int i = 0; i < tr; i++) {
			int people = Integer.parseInt(st.nextToken());
			trs[i] = people;
			isTrue[people] = true;
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());

			s = Integer.parseInt(st.nextToken());
			members = new int[s];

			for (int j = 0; j < s; j++) {
				members[j] = Integer.parseInt(st.nextToken());
			}

			parties.add(members);

			for (int j = 0; j < s; j++) {
				ArrayList<Integer> list = near.get(members[j]);

				for (int k = 0; k < s; k++) {
					if (j != k) list.add(members[k]);
				}
			}
		}

		for (int i = 0; i < tr; i++) {
			dfs(trs[i]);
		}

		for (int[] party : parties) {
			for (int member : party) {
				if (isTrue[member]) {
					m--;
					break;
				}
			}
		}

		System.out.println(m);
	}

	private static void dfs(int cur) {
		isUsed[cur] = true;
		isTrue[cur] = true;

		for (int next : near.get(cur)) {
			if (isUsed[next]) continue;
			dfs(next);
		}
	}
}

문제

접근 방식

각각의 구슬을 정점, 두 구슬의 대소 관계를 간선이라고 했을 때

정점 X에서 Y로 갈 수 있다면 구슬 X가 구슬 Y보다 무겁다는 것을 알 수 있다.

하지만 단방향 그래프로 인접 행렬을 표현하니 대소 관계가 제대로 처리가 되지 않고

일반적인 양방향으로 표현하자니 어느 구슬이 무거운지를 알 수가 없는 문제가 있었다.

그래서 인접 행렬을 만들 때 구슬 X가 Y보다 무겁다면

정점 X에서 Y로 갈 수 있는 것을 표시할 때 1로 표시를 해주고

구슬 X가 Y보다 가볍다면 -1로 표시를 해주었다.

그 후 각 구슬마다 DFS로 탐색을 해주면서

다음 방문할 정점이 1인지 -1인지에 따라

각 수마다 더 큰 수와 작은 수의 개수를 카운트 해주고

모든 정점에 대한 탐색이 끝나면 카운트를 저장해둔 배열을 순회하며

X보다 무겁거나 가벼운 구슬의 개수가 (n+1)/2 이상이면

중간값이 될 수 없다는 것을 알 수 있다.

풀이

public class Main {

	private static int n;
	private static int next;
	private static int[][] near;
	private static int[][] count;
	private static boolean[] isVisited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		near = new int[n + 1][n + 1];
		count = new int[n + 1][2];

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			near[x][y] = 1;
			near[y][x] = -1;
		}

		for (int i = 1; i <= n; i++) {
			isVisited = new boolean[n + 1];
			dfs(i, i, 0);
		}

		int max = 0;
		int mid = (n + 1) / 2;

		for (int i = 1; i <= n; i++) {
			if(count[i][0] >= mid || count[i][1] >= mid) max++;
		}

		System.out.println(max);
	}



	private static void dfs(int start, int cur, int x) {
		isVisited[cur] = true;
		if(x != 0) count[start][x == 1 ? 0 : 1]++;

		for (int i = 1; i <= n; i++) {
			next = near[cur][i];
			if (isVisited[i] || next == 0) continue;
			if (x != 0 && next != x) continue;
			dfs(start, i, next);
		}
	}
}