[코드트리 - L12] 25년 상반기 오전 1번 민트초코우유

 

 

 

코딩테스트 기출 문제 설명: 민트 초코 우유 | 코드트리

 

 

문제 풀이

조건을 잘 봐야 한다. 풀이하다가 조건을 잊어서 히든 테케에서 발견하기 ㅠ 그래도 하반기 문제들보다는 정렬만 잘하면 괜찮다고 느껴졌던 문제

 

빠트렸던 조건들

• 저녁시간에서 전파할 때, 그룹 순서와 같은 그룹 내 순서를 잊지 말 것!
• 전파 전, 같은 신봉음식일 경우를 확인하여 넘기기(강한 전파 구문 안에 넣어서 틀렸었다!)
• 비트 마스킹을 쓰면, T, C, M 확인 방법이 더 간단할 것 같은데 우선순위를 지정해주는 방식으로 구분하였다.

 

전체 코드

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

public class Main {

	static class Node implements Comparable<Node> {
		int x, y, power;
		String like;

		Node(int x, int y, String like, int power) {
			this.x = x;
			this.y = y;
			this.like = like;
			this.power = power;
		}

		@Override
		public int compareTo(Node o) {

			if (o.power != this.power) {
				return o.power - this.power; // 내림차순ㄴ
			} else if (o.x != this.x) {
				return this.x - o.x;
			}
			return this.y - o.y;
		}

	}

	static int N, T;
	static String[][] map;
	static int[][] faith;
	static int[] dx = { -1, 1, 0, 0 }; // 상하좌우
	static int[] dy = { 0, 0, -1, 1 };
	static List<Node> leader;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input;

		input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		T = Integer.parseInt(input[1]); // 일수

		map = new String[N][N];

		// T: 민트, C: 초코, M: 우유
		// 가능 조합: TCM, TC, TM, CM, T, C, M
		for (int i = 0; i < N; i++) {
			input = br.readLine().split("");
			for (int j = 0; j < N; j++) {
				map[i][j] = input[j];
			}
		}

		// 신앙심
		faith = new int[N][N];
		for (int i = 0; i < N; i++) {
			input = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				faith[i][j] = Integer.parseInt(input[j]);
			}
		}

		for (int t = 0; t < T; t++) {

			leader = new ArrayList<>();
			morning();
			lunch();
			evening();

			// TCM, TC, TM, CM, M, C, T 순으로 출력
			String[] printMap = { "TCM", "TC", "TM", "CM", "M", "C", "T" };
			for (String m : printMap) {
				print(m);
			}
			System.out.println();
		}

	}

	static String normalize(String s) {
		boolean t = false, c = false, m = false;

		for (char ch : s.toCharArray()) {
			if (ch == 'T')
				t = true;
			else if (ch == 'C')
				c = true;
			else if (ch == 'M')
				m = true;
		}

		StringBuilder sb = new StringBuilder();
		if (t)
			sb.append("T");
		if (c)
			sb.append("C");
		if (m)
			sb.append("M");

		return sb.toString();
	}

	static void print(String target) {

		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j].equals(target)) {
					sum += faith[i][j];
				}
			}
		}

		System.out.print(sum + " ");
	}

	static int getRank(String s) {
		if (s.length() == 1) {
			return 1;
		} else if (s.length() == 2) {
			return 2;
		}
		return 3;
	}

	// 3. 저녁: 대표자들이 전파 시작
	private static void evening() {

		// 전파를 그룹 순으로 정렬
		Collections.sort(leader, (a, b) -> {

			// 1. 음식 그룹순(단일, 이중, 삼중)
			int ta = getRank(a.like);
			int tb = getRank(b.like);
			if (ta != tb)
				return ta - tb; // 오름차순

			// 2. 신앙심 높은 순(내림차순)
			if (faith[a.x][a.y] != faith[b.x][b.y]) {
				return faith[b.x][b.y] - faith[a.x][a.y];
			}

			// 3. 행번호 작은 순
			if (a.x != b.x)
				return a.x - b.x;

			// 열 번호 작은 순
			return a.y - b.y;
		});

		boolean[][] blocked = new boolean[N][N];
		for (Node lead : leader) {

			// 전파당했으면, 방어상태 전환
			if (blocked[lead.x][lead.y])
				continue;

			// 전파 방향
			int dir = faith[lead.x][lead.y] % 4;
			// 간절함
			int x = faith[lead.x][lead.y] - 1;
			faith[lead.x][lead.y] = 1;

			int sx = lead.x, sy = lead.y;

			while (true) {

				int nx = sx + dx[dir];
				int ny = sy + dy[dir];

				// 범위 벗어나고, 간절함 0이면 멈춤
				if (!isRange(nx, ny) || x == 0) {
					break;
				}

				// 같으면 그냥 지나감
				if (map[nx][ny].equals(lead.like)) {
					sx = nx;
					sy = ny;
					continue;
				}

				// 강한 전파
				if (x > faith[nx][ny]) {

					map[nx][ny] = lead.like;
					x -= (faith[nx][ny] + 1);
					faith[nx][ny] += 1;
					blocked[nx][ny] = true;

				} else { // 약한 전파

					map[nx][ny] = normalize(map[nx][ny] + lead.like);
					faith[nx][ny] += x;
					x = 0;
					blocked[nx][ny] = true;
				}

				sx = nx;
				sy = ny;
				if (x <= 0) {
					break;
				}
			}

		}
	}

	// 2. 점심: 그룹 대표자에게 신앙심 이전
	private static void lunch() {

		// dfs로 같은 그룹 확인
		boolean[][] visited = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				PriorityQueue<Node> tmp = new PriorityQueue<>();
				if (!visited[i][j]) {
					Node l = dfs(i, j, visited, tmp);

					int propa = tmp.size() - 1; // 전파 할 힘
					while (!tmp.isEmpty()) {
						Node stu = tmp.poll();
						if (l.x == stu.x && l.y == stu.y) {
							faith[l.x][l.y] += propa;
						} else {
							faith[stu.x][stu.y]--;
						}
					}

					leader.add(new Node(l.x, l.y, l.like, l.power + propa));

				}
			}
		}

	}

	// 같은 그룹대 대표자 구해서 반환
	private static Node dfs(int x, int y, boolean[][] visited, PriorityQueue<Node> tmp) {

		visited[x][y] = true;
		tmp.add(new Node(x, y, map[x][y], faith[x][y]));

		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];

			if (!isRange(nx, ny))
				continue;

			if (!visited[nx][ny] && map[x][y].equals(map[nx][ny])) {
				dfs(nx, ny, visited, tmp);
			}
		}

		return tmp.peek();
	}

	// 1. 아침: 모든 학생의 신앙심 +1
	private static void morning() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				faith[i][j] += 1;
			}
		}
	}

	static boolean isRange(int x, int y) {
		if (x < 0 || x >= N || y < 0 || y >= N) {
			return false;
		}
		return true;
	}

}