백준 23289번 : 온풍기 안녕! [Java]

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

문제 탐색하기

....어제 푼 문제가 어지럽다고 말한걸 취소하고 싶을 정도로 머리가 아득해졌다. 하지만...잘 문제를 살펴보자. 구현 문제는 문제를 똑바로 읽는 거부터 시작하면 된다. 아래 순서대로 구현하면 되는데 각각에 설명이 부족한 부분들이 존재하기에 파악하기 힘들다. 찬찬히 살펴보도록 하자. 먼저 구현해야할 순서는 아래와 같다.

 

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
2. 온도가 조절됨
3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
4. 초콜릿을 하나 먹는다.
5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.

처음에 배열을 잘 설계했다는 가정 하에 사실 구현 순서가 위와 꼭 같아야 할 필요는 없다. 비교적 구현하기 쉬운 3, 4, 5번을 먼저 하고 1, 2번을 하는 전략으로 구현해도 괜찮다. 이 문제에서 구현해야할 때 유의 해야할 점은 아무래도 1번과 2번이다.

 

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴

예제를 보면 바로 알 수 있듯이 온도가 1에 다할 때까지 바람이 전파되는 것을 구현해야 한다. 처음 시도할 때는 bfs를 통해서 근처의 것들을 하나 씩 처리하는 방법을 구현해보려 했으나 분기를 나누기가 상당히 까다로웠다. 이에 따라서 dfs로 변경하여 깊은 곳을 제일 먼저 탐색하도록 하였다.

 

여기서 까다로운 부분은 이뿐만이 아니다. 대각선에 대한 예제가 하나 밖에 나와있지 않은데. 실제로 온풍기 방향에 따라서 검사해야할 벽의 순서가 달라진다. 온풍기가 1, 2 방향인 경우 (왼쪽이나 오른쪽일 때)는 x축으로 먼저 탐색해야 하지만, 온풍기가 3, 4 방향인 경우 y축으로 먼저 탐색해야 한다. 이 부분을 놓쳐서 한참을 애먹었다.

 

2. 온도가 조절됨

이는 새로운 2차원 배열을 만들고 기존의 온도와 주변 온도를 재분배한 것을 기록하여야 한다. 이 때 유의해야할 점은 벽이 있는 것을 확인해야하고, 이미 한 번 계산을 했다면 반복해서 계산 해서는 안된다. 이에 따라서 계산 했던 방향과 계산 된 방향을 기록하기 위해서 3차원 배열을 통해서 진입한 좌표와 진입된 좌표를 체크해서 2번 이상 계산 되지 않도록 구현하면 될 것 같다. 처음엔 비트필드를 사용하는 방법도 생각했는데, 메모리 제한이 크고 배열을 사용하는 법이 구현하기 수월할것 같아서 배열을 사용해 보았다.

 

코드 구현하기

1. 온도, 지도를 2차원 배열을 통해서 기록해둔다. 벽의 경우 set를 통해서 중복을 제거하고 양방향으로 참조할 수 있도록 구현해둔다.
2. 반복문을 구현한다.
   1. 모든 온풍기를 통해서 바람이 나오는 연산을 dfs를 통해서 구현한다. 이 때 온풍기 방향에 따라서 대각선일 때 어떤 방향을 먼저 확인할 지 고려하여 구현한다. 
   2. 온도가 조절되는 연산을 완전 탐색을 통하여 구현한다. 초기의 온도 값이 필요하므로 기존 온도 배열의 값을 복사한다.
   3. 가장 바깥 쪽의 온도를 1 줄이는 연산을 구현한다. 0 이상일 때만 줄이도록 구현해야한다.
   4. 초콜릿을 하나 더한다.
   5. 5에 해당하는 좌표를 미리 리스트에 넣어두고 해당 온도가 K이상인지 확인한다. K이상일 경우 반복문을 탈출한다.
3. 먹은 초콜릿의 개수가 101이 넘어가지 않도록 반복문을 설정하고 반복문이 끝나면 해당 개수를 출력한다.

풀이

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

public class Main {
	static int R, C, K, W, chocolate = 0;
	static int[][] map;
	static int[][] temperatures;
	/*
		1: 방향이 오른쪽인 온풍기가 있음
		2: 방향이 왼쪽인 온풍기가 있음
		3: 방향이 위인 온풍기가 있음
		4: 방향이 아래인 온풍기가 있음
	 */
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	static boolean[][] visited;
	static int[][][] windDirections = {{{0, 1}, {-1, 1}, {1, 1}}, {{0, -1}, {-1, -1}, {1, -1}},
		{{-1, 0}, {-1, -1}, {-1, 1}}, {{1, 0}, {1, -1}, {1, 1}}};
	static HashMap<Point, HashSet<Point>> walls = new HashMap<>();
	static ArrayList<Heater> heaters = new ArrayList<>();
	static ArrayList<Point> searchPoints = new ArrayList<>();

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		R = fr.nextInt();
		C = fr.nextInt();
		K = fr.nextInt();
		map = new int[R][C];
		temperatures = new int[R][C];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				int now = fr.nextInt() - 1;
				map[i][j] = now;
				if (0 <= now && now <= 3) {
					heaters.add(new Heater(i, j, now));
				} else if (now == 4) {
					searchPoints.add(new Point(i, j));
				}
			}
		}

		W = fr.nextInt();
		for (int i = 0; i < W; i++) {
			makeWall(fr.nextInt() - 1, fr.nextInt() - 1, fr.nextInt());
		}

		for (int i = 0; i < 101; i++) {
			// 모든 온풍기에서 따뜻한 바람이 나옴
			for (Heater h : heaters) {
				heatUp2(h);
			}

			// 온도 조절
			evenTemp();

			// 온도 감소
			chill();

			// 초콜릿 먹기
			chocolate++;

			// 조사하는 모든 칸의 온도가 K 이상인지 검사하기.
			if (inspect()) {
				break;
			}
		}

		System.out.println(chocolate);
	}


	static void makeWall(int x, int y, int t) {
		Point p1 = new Point(x, y);
		Point p2 = (t == 0) ? new Point(x - 1, y) : new Point(x, y + 1);
		walls.computeIfAbsent(p1, k -> new HashSet<>()).add(p2);
		walls.computeIfAbsent(p2, k -> new HashSet<>()).add(p1);
	}

	static void heatUp2(Heater heater) {
		visited = new boolean[R][C];
		int nx = heater.x + dx[heater.dir];
		int ny = heater.y + dy[heater.dir];
		if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
			return;
		}
		dfs(nx, ny, 5, heater);
	}

	static void dfs(int x, int y, int count, Heater heater) {
		if (count == 0) {
			return;
		}
		visited[x][y] = true;
		temperatures[x][y] += count;
		for (int i = 0; i < 3; i++) {
			int dx = windDirections[heater.dir][i][0];
			int dy = windDirections[heater.dir][i][1];
			int nx = x + dx;
			int ny = y + dy;
			if (nx < 0 || ny < 0 || nx >= R || ny >= C || visited[nx][ny]) {
				continue;
			}

			if(dx == 0 || dy == 0) {
				if (!checkWall(new Point(x, y), new Point(nx, ny))) {
					dfs(nx, ny, count - 1, heater);
				}
			} else if (heater.dir == 0 || heater.dir == 1) {
				Point diagonal = new Point(x + dx, y);
				if (!checkWall(new Point(x, y), diagonal)) {
					if (!checkWall(diagonal, new Point(x + dx, y + dy))) {
						dfs(nx, ny, count - 1, heater);
					}
				}
			} else if (heater.dir == 2 || heater.dir == 3) {
				Point diagonal = new Point(x, y + dy);
				if (!checkWall(new Point(x, y), diagonal)) {
					if (!checkWall(diagonal, new Point(x + dx, y + dy))) {
						dfs(nx, ny, count - 1, heater);
					}
				}
			}
		}
	}

	static void evenTemp() {
		int[][] newTemp = new int[R][C];
		boolean[][][] visited = new boolean[R][C][4];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				newTemp[i][j] = temperatures[i][j];
			}
		}

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
						continue;
					}

					if (checkWall(new Point(i, j), new Point(nx, ny))) {
						continue;
					}

					int indegreeDir = reverseDirection(k);
					if (!visited[nx][ny][indegreeDir]) {
						visited[nx][ny][indegreeDir] = true;
						visited[i][j][k] = true;
						int diff = Math.abs(temperatures[i][j] - temperatures[nx][ny]) / 4;
						if (temperatures[i][j] > temperatures[nx][ny]) {
							newTemp[i][j] -= diff;
							newTemp[nx][ny] += diff;
						} else if (temperatures[i][j] < temperatures[nx][ny]) {
							newTemp[i][j] += diff;
							newTemp[nx][ny] -= diff;
						}
					}
				}
			}
		}

		temperatures = newTemp;
	}

	static int reverseDirection(int dir) {
		if (dir == 0) {
			return 1;
		} else if (dir == 1) {
			return 0;
		} else if (dir == 2) {
			return 3;
		} else
			return 2;

	}

	static boolean checkWall(Point o, Point other) {
		return walls.containsKey(o) && walls.get(o).contains(other);
	}

	static void chill() {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (i == 0 || i == R - 1 || j == 0 || j == C - 1) {
					if (temperatures[i][j] > 0) temperatures[i][j]--;
				}
			}
		}
	}

	static boolean inspect() {
		for (Point sp : searchPoints) {
			if (temperatures[sp.x][sp.y] < K) {
				return false;
			}
		}
		return true;
	}

	static void printTemp(String result) {
		System.out.println(result);
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				System.out.print(temperatures[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("________________________________________");
	}

	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}

	static class Point {
		int x, y, k;

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

		public Point(int x, int y, int k) {
			this.x = x;
			this.y = y;
			this.k = k;
		}

		@Override
		public boolean equals(Object o) {
			if (o instanceof Point) {
				Point p = (Point)o;
				return x == p.x && y == p.y;
			}
			return false;
		}

		@Override
		public int hashCode() {
			return (x + "," + y).hashCode();
		}
	}

	static class Heater {
		int x, y, dir;

		public Heater(int x, int y, int dir) {
			this.x = x;
			this.y = y;
			this.dir = dir;
		}

		@Override
		public String toString() {
			return "(" + x + "," + y + "," + dir + ")";
		}
	}
}