[BOJ] 백준 23289 온풍기 안녕!

Approach

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

시뮬레이션 문제로 여러 문제 조건이 난이도가 어느정도 있는 문제인 것 같다.

시험장에서 Test Fail 되는 경우 디버깅하기 쉽지 않을 것 같네요 🤨

📌 삼성 SW 기출 모음

[문제 모음] 삼성 sw 기출 (코딩 테스트)

---

시뮬레이션은 구현 순서는 아래와 같다.

0. 먹은 초콜릿 개수는 100을 넘어가면 101 출력되도록 while문 조건 처리
1. 온풍기 가동
2. 온도 조절
3. 바깥쪽 온도 조절
4. 초콜릿을 하나 먹는다.
5. 조사하는 모든 칸의 온도가 K 이상인지 확인

✔️ 각 모듈별로 잘 설계해놓는다면 단계별로 디버깅하기 좀 더 수월해질 것 같다.

     특히, <1. 온풍기 가동>와 <2. 온도 조절>을 잘 설계해야 했다.

① 온풍기와 조사해야 하는 칸의 정보

• 온풍기 정보를 입력받을 때, 방향을 임의로 설계한 방향으로 조정

  문제에서는 {1: 오른쪽, 2: 왼쪽, 3: 위, 4: 아래} 으로 주어지기에

  wDir[] = { 0, RIGHT, LEFT, UP, DOWN };

  배열 시작인덱스 조정과 가독성을 위해서 enum 사용

• map[][] 에는 온도 수치만 표시

  온풍기 위치, 조사해야 하는 칸은 별도의 Queue로 관리

  (0: 빈칸,  1~4: 온풍기, 5: 조사해야 할 좌표)

 

② 벽(wall)의 정보

• (t == 0): (x, y)와 (x-1, y) 사이에 벽

• (t == 1): (x, y)와 (x, y+1) 사이에 벽

ex) [윗 좌표에서 바라보는 아래 벽]과 [아래 좌표에서 바라보는 윗 벽]

      좌표에 따라 방향은 다르지만 위치상 같은 벽인 셈이다.

✔️ 하나의 좌표에서 벽은 상/하/좌/우 존재할 수 있기 때문에

      wall[MAX_RC][MAX_RC][4]로 처리

 

온풍기 가동

온풍기는 방향에 따라 3곳으로 이동한다.

이때 진행방향에 따라서 확인해야하는 벽의 위치와 개수가 다르다.

 

ex) 오른쪽 방향을 바라보는 온풍기(x, y) 기준

① ↑→ : (x, y)와 (x-1, y) 사이의 벽 & (x-1, y)와 (x-1, y+1) 사이의 벽

② → : (x, y)와 (x, y+1) 사이의 벽

③ ↓→ : (x, y)와 (x+1, y) 사이의 벽 & (x+1, y)와 (x+1, y+1) 사이의 벽

▶ (x, y)를 시작으로 (x-1, y+1), (x, y+1), (x+1, y+1) 로 이동한다.

    "시작 좌표" "도착 좌표" "어떤 방향으로 왔는지" 확인해서 처리

각 방향에서 통과해야 하는 벽이 없는지를 확인하였으면

대각선 방향은 2개의 벽을 통과해야 하며, 직선 방향은 1개의 벽을 통과해야 한다.

 

예를 들어, 동쪽으로 바라보는 온풍기 기준

(x, y)에서 (x-1, y+1)로 대각선 방향으로 이동할 때,

→ wall[x][y][UP] 과 wall[x-1][y][RIGHT]에 벽이 없어야 한다.

    물론 벽 위치상 각각 wall[x-1][y][DOWN] 와 wall[x-1][y+1][LEFT]에 해당된다.

 

온풍기과 바라보는 방향, 실제 바람이 퍼져가는 방향을 LUT로 처리.

📌 [알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)

[알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)

 

중복 방문 처리

그림에서 화살표 표시해둔 곳을 보면

BFS 진행 방향에 따라 중복되는 칸이 발생할 수 있다.

그렇기 때문에 visited[MAX_RC][MAX_RC] 처리

 

① 각 온풍기가 작동할 때마다 visited[][] 초기화

② 온풍기에서 처음 시작하는 곳을 첫번째 원소로 삽입

    처음 더해지는 온도 = 5

③ Queue에서 하나씩 빼내면서 map[][]에 온도를 더해준다.

④ 퍼져나가는 온도 = 1 인 경우에는 계속 퍼져나가지 않도록 처리

⑤ 온풍이 3가지 목표지점으로 진행되는데, 

    범위•중복•벽 여부 확인

 

BFS 구현하는 것에서도 문제 적용이 쉽지 않은 편인 것 같다.

📌 BFS (Breadth-First Search, 너비 우선 탐색)

BFS (Breadth-First Search, 너비 우선 탐색)

 

온도조절

그림에서 표시한 곳들에 대해 살펴보자.

① 5  ▶ 12

    (18 - 5) / 4 → 3

    (23 - 5) / 4 → 4

    → 5 + 3 + 4 = 12

 

② 0  ▶ 33

    (70 - 0) / 4 →17

    (46 - 0) / 4 → 11

    (20 - 0) / 4 → 5

    → 0 + 17 + 11 + 5 = 33

 

좌표간 온도 비교는 한번만 이루어지면 된다.

동시에 온도조절이 되기 때문에 

복사본 cMap[][]에서 진행한 후 원본 map[][]에 반영

① 좌표끼리 온도가 중복되지 않기 위해서

    map[][] 탐색 방향에 맞춰 오른쪽과 아래 좌표만 비교.

    Dir[] = { RIGHT, DOWN };

② 두 칸 사이에 벽이 있으면 온도가 조절되지 않는다.

③ 두 칸의 온도를 비교한 후 절대값 수치로

    높은 칸이 온도 감소, 낮은 칸이 온도 증가할 수 있도록 처리

 

 

바깥쪽 온도 처리

map[][]에서 가장 바깥쪽 칸의 온도를 1씩 감소하는 작업이다.

• map[][] 크기가 R × C 로 입력받는 숫자에 따라 다르다.

• 온도가 1 이상인 칸의 온도가 1씩 감소한다.

→ 그림에 표시한 4개 영역을 for 문으로 구현.

 

조사하는 모든 칸의 온도 확인

조사하는 칸을 targetQ에서 하나씩 꺼내어(?)

해당하는 칸의 온도가 모두 K 이상인지 확인한다.

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

enum
{
	RIGHT, LEFT, DOWN, UP,
};

struct Node
{
	int x, y, state;
};

const int wdx[][3] = { { -1, 0, 1 }, {-1, 0, 1 }, {1, 1, 1}, {-1, -1, -1} };
const int wdy[][3] = { { 1, 1, 1}, { -1, -1, -1 }, {-1, 0, 1 },{-1, 0, 1} };
const int wallCnt[] = { 2, 1, 2 }; // 온풍기 방향에 따른 확인해야 하는 벽의 개수
const int wallPos[3][2][4][3] =	   // 온풍기 방향에 따른 벽 위치
{
	{	// upward diagonal
		{ {0, 0, UP}, {0, 0, UP}, {0, 0, LEFT}, {0, 0, LEFT}},
		{ {-1, 0, RIGHT}, {-1, 0, LEFT}, {0, -1, DOWN}, {0, -1, UP}}
	},
	{	// straight
		{ {0, 0, RIGHT}, { 0, 0, LEFT }, { 0, 0, DOWN }, { 0, 0, UP }},
		{ {-1, -1, -1}, {-1, -1, -1}, {-1, -1, -1}, {-1, -1, -1} }
	},
	{	// down diagonal
		{ {0, 0, DOWN}, {0, 0, DOWN}, {0, 0, RIGHT}, {0, 0, RIGHT}},
		{ {1, 0, RIGHT}, {1, 0, LEFT}, {0, 1, DOWN}, {0, 1, UP}}
	}
};

const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
const int wDir[] = { 0, RIGHT, LEFT, UP, DOWN };
const int tDir[] = { RIGHT, DOWN };

int R, C, K, W, ans;
const int MAX_RC = 20 + 2;
int map[MAX_RC][MAX_RC];
bool wall[MAX_RC][MAX_RC][4];

vector<Node> targetQ, heaterQ;

inline void _memcpy(int dest[][MAX_RC], int src[][MAX_RC])
{
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			dest[i][j] += src[i][j];
		}
	}
}

void input()
{
	scanf("%d %d %d", &R, &C, &K);
	int x, y, t;
	for (x = 1; x <= R; x++)
	{
		for (y = 1; y <= C; y++)
		{
			scanf("%d", &t);
			if (1 <= t && t <= 4) // 온풍기
			{
				heaterQ.push_back({ x, y, wDir[t] });
			}
			if (t == 5) // 조사 대상
			{
				targetQ.push_back({ x, y });
			}
		}
	}

	scanf("%d", &W); // 벽 정보 입력
	for (int i = 0; i < W; i++)
	{
		scanf("%d %d %d", &x, &y, &t);
		if (t == 0)
			wall[x][y][UP] = wall[x - 1][y][DOWN] = true;
		else
			wall[x][y][RIGHT] = wall[x][y + 1][LEFT] = true;
	}
}

bool isNotWall(int x, int y, int dir, int nextDir)
{
	int passCnt = 0;
	for (int i = 0; i < wallCnt[nextDir]; ++i)
	{
		int nextX = x + wallPos[nextDir][i][dir][0];
		int nextY = y + wallPos[nextDir][i][dir][1];
		int nWall = wallPos[nextDir][i][dir][2];
		if (!wall[nextX][nextY][nWall]) passCnt++;
	}

	// 해당 방향에서 지나가야 하는 모든 벽을 통과한 경우
	return passCnt == wallCnt[nextDir] ? true : false;
}

void heaterOn()
{
	for (int i = 0; i < heaterQ.size(); i++)
	{
		bool visited[MAX_RC][MAX_RC] = { false, };
		int dir = heaterQ[i].state;

		queue<Node> que;
		que.push({ heaterQ[i].x + dx[dir], heaterQ[i].y + dy[dir], 5 });

		while (!que.empty())
		{
			Node cur = que.front();
			que.pop();

			map[cur.x][cur.y] += cur.state;

			if (cur.state == 1)
				continue;

			for (int nextDir = 0; nextDir < 3; nextDir++)
			{
				int nextX = cur.x + wdx[dir][nextDir];
				int nextY = cur.y + wdy[dir][nextDir];
				if (nextX < 1 || nextY < 1 || nextX > R || nextY > C)
					continue;

				if (visited[nextX][nextY])
					continue;

				if (!isNotWall(cur.x, cur.y, dir, nextDir))
					continue;

				visited[nextX][nextY] = true;
				que.push({ nextX, nextY, cur.state - 1 });
			}
		}
	}
}

void controlTemperature()
{
	int cMap[MAX_RC][MAX_RC] = { 0, };

	for (int x = 1; x <= R; x++)
	{
		for (int y = 1; y <= C; y++)
		{
			for (int i = 0; i < 2; i++)
			{
				int nextX = x + dx[tDir[i]];
				int nextY = y + dy[tDir[i]];

				if (nextX < 1 || nextY < 1 || nextX > R || nextY > C)
					continue;

				if (wall[x][y][tDir[i]])  // 벽이 있는 경우
					continue;

				int diff = (abs(map[x][y] - map[nextX][nextY])) / 4;

				if (map[x][y] > map[nextX][nextY])
				{
					cMap[x][y] -= diff;
					cMap[nextX][nextY] += diff;
				}
				else
				{
					cMap[nextX][nextY] -= diff;
					cMap[x][y] += diff;
				}
			}
		}
	}
	_memcpy(map, cMap);
}

void sideTemperatureDown()
{
	for (int x = 1; x < R; ++x) if (map[x][1] > 0) map[x][1]--;
	for (int y = 1; y < C; ++y) if (map[R][y] > 0) map[R][y]--;
	for (int x = R; x > 1; --x) if (map[x][C] > 0) map[x][C]--;
	for (int y = C; y > 1; --y) if (map[1][y] > 0) map[1][y]--;
}

inline bool tagetCheck()
{
	for (int i = 0; i < targetQ.size(); i++)
	{
		if (map[targetQ[i].x][targetQ[i].y] < K)
			return false;
	}
	return true;
}

int main()
{
	// freopen("Input.txt", "r", stdin);
	input();

	while (ans <= 100)				// 0. 먹은 초콜릿 개수는 100 이하이도록
	{
		heaterOn();					// 1. 온풍기 가동
		controlTemperature();		// 2. 온도 조절
		sideTemperatureDown();		// 3. 바깥쪽 온도 조절
		ans++;						// 4. 초콜릿을 하나 먹는다.
		if (tagetCheck()) break;	// 5. 조사하는 모든 칸의 온도가 K 이상인지 확인
	}

	printf("%d\n", ans);
}

---

📌 함께 보면 좋은 포스팅

• 삼성 SW 기출 모음

• 삼성 SW 코딩 테스트 준비(A형)

• [알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)

• BFS (Breadth-First Search, 너비 우선 탐색)