99클럽 코테 스터디 8일차 TIL

비기너

문제

25593번: 근무 지옥에 빠진 푸앙이 (Small)

# 맵

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

풀이

모든 근무자의 근무 시간이 12시간 이하로 차이 나는지 확인하는 문제이다.

맵을 이용하여 각 근무자의 근무시간을 저장한다.

맵을 순회하며 근무자의 근무 시간 차이가 12시간 이하인지 확인한다.

근무자가 없어도 공평하게 근무한 것으로 판단하므로 맵이 비어있으면 공평하게 근무한 것이다. 

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		HashMap<String, Integer> mp = new HashMap<>();

		for (int i = 0; i < n; i++) {
			int[] t = { 4, 6, 4, 10 };
			for (int j = 0; j < 4; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int k = 0; k < 7; k++) {
					String s = st.nextToken();
					if (s.equals("-"))
						continue;
					if (mp.containsKey(s))
						mp.put(s, mp.get(s) + t[j]);
					else
						mp.put(s, t[j]);
				}
			}
		}

		if (mp.isEmpty()) {
			bw.write("Yes");
			bw.flush();
			bw.close();
			return;
		}

		for (int i : mp.values()) {
			for (int j : mp.values()) {
				if (Math.abs(i - j) > 12) {
					bw.write("No");
					bw.flush();
					bw.close();
					return;
				}
			}
		}

		bw.write("Yes");
		bw.flush();
		bw.close();
	}
}

미들러

문제

2644번: 촌수계산

# bfs

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

풀이

두 사람 간의 촌수 관계를 구하는 문제이다.

촌수 관계는 친척 관계를 그래프로 표현했을 때 두 사람 간의 최단거리이다.

따라서 bfs를 이용하면 촌수 관계를 구할 수 있다.

코드

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

public class Main {
	static int n, m, a, b;
	static int[] visited;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

	static void bfs(int x) {
		Queue<Integer> q = new LinkedList<>();
		q.add(x);
		visited[x] = 1;
		while (!q.isEmpty()) {
			x = q.poll();
			if (x == b)
				break;
			for (int nx : adj.get(x)) {
				if (visited[nx] >= 1)
					continue;
				q.add(nx);
				visited[nx] = visited[x] + 1;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(br.readLine());

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

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			adj.get(x).add(y);
			adj.get(y).add(x);
		}

		visited = new int[n + 1];
		bfs(a);

		bw.write((visited[b] - 1) + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

4483번: 녹색 옷 입은 애가 젤다지?

# 다익스트라

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

풀이

동굴을 지나갈 때 잃는 루피의 최솟값을 구하는 문제이다.

지나갈 때 잃는 루피를 경로의 가중치라고 하면 가중치가 있는 그래프에서 최단거리를 구하는 문제이다.

가중치가 있는 그래프에서 최단거리를 구하려면 다익스트라 알고리즘을 이용하면 된다.

코드

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

class Node implements Comparable<Node> {
	int y, x, c;

	public Node(int y, int x, int c) {
		this.y = y;
		this.x = x;
		this.c = c;
	}

	@Override
	public int compareTo(Node n) {
		return this.c - n.c;
	}
}

public class Main {
	static int n;
	static int[][] a, d;
	static int[] dy = { 1, -1, 0, 0 };
	static int[] dx = { 0, 0, 1, -1 };

	static void dijkstra() {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		d = new int[n][n];
		for (int i = 0; i < n; i++)
			Arrays.fill(d[i], 1000000000);
		pq.add(new Node(0, 0, a[0][0]));
		d[0][0] = a[0][0];

		while (!pq.isEmpty()) {
			Node node = pq.poll();
			int y = node.y, x = node.x, c = node.c;

			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || ny >= n || nx >= n)
					continue;
				if (c + a[ny][nx] < d[ny][nx]) {
					d[ny][nx] = c + a[ny][nx];
					pq.add(new Node(ny, nx, d[ny][nx]));
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int idx = 0;
		while (true) {
			idx++;
			n = Integer.parseInt(br.readLine());
			if (n == 0)
				break;
			a = new int[n][n];

			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++)
					a[i][j] = Integer.parseInt(st.nextToken());
			}

			dijkstra();

			bw.write("Problem " + idx + ": " + d[n - 1][n - 1] + "\n");
		}

		bw.flush();
		bw.close();
	}
}