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

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

23289번: 온풍기 안녕!

문제 이해

온풍기에서 바람 나오는 거랑 벽 확인하는 것이 굉장히 까다로운 문제이다

사실 벽에 부딪히는 것을 어떻게 처리해야하나 하고 인터넷 검색을 통해 해결했는데, 

오랫동안 문제를 이해하지 못한 것은 내가 문제를 제대로 읽지 않았기 때문이다!

 

문제는 

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

나와있는 단계를 그대로 구현하면 된다. 단지 함수 하나하나를 구현하기가 어려울 뿐...

 

1. 벽의 입력 ( Get_Input() 중 )

이렇게 그림을 그려서 정리를 해야 하는데, 그냥 보려니까 x,y가 헷갈리고 막 그런다.

암튼 이렇게 해서 벽은 wall이라는 배열에 각 좌표의 4방향 중 어디가 막혔는지를 표시하면 된다. 

if (t == 0) {
  wall[y][x][NORTH] = 1;
  wall[y - 1][x][SOUTH] = 1;
}
else {
  wall[y][x][EAST] = 1;
  wall[y][x+1][WEST] = 1;
}

2. 바람이 퍼지는 모양 ( BFS() )

바람의 방향이 동서남북 중 어디냐에 따라서 바람이 퍼져나가는 모양이 다르다.

그래서 바람의 방향 별로 퍼져나가는 좌표를 wdy와 wdx 좌표에 미리 정의해둔다.

wdy[0]의 세 좌표는 이면 바람이 동쪽 방향일 때 좌측, 중간, 우측 칸의 y좌표이다.

wdx[0]의 세 좌표는 이면 바람이 동쪽 방향일 때 좌측, 중간, 우측 칸의 x좌표이다.

이런 식으로 되는데, 각 방향에 대해서 다 다르니까 주의해야 한다.

 

3. 벽으로 인해 막히는 경우 (Check_Wall())

BFS를 할 때 막히는 경우를 확인해야 하는데, 한 칸에서 다른 칸으로 갈 때 벽에 막히는 경우는 다음과 같은 경우이다

 

바람의 방향이 EAST인 경우에, 

좌측 (y, x) --> (y-1, x+1) 으로 가는 경우에는 

빨간 선이 있는 그 쪽 면에 벽이 있으면 안되는 것이다. 즉, 원래 있던 칸의 EAST와 가려는 칸의 SOUTH에 벽이 있으면 안된다.

 

이런식으로 정리를 하면 이렇게 된다:

이렇게 정리하고 Check_Wall()을 노가다로 구현했다

int Check_Wall(int y, int x, int ny, int nx, int d, int i) {
	if (i == 1) {
		// 중간
		if (wall[y][x][d] == 0) return 1;
	}
	else if (i == 0) {
		// 좌측
		if (d == EAST) {
			if (wall[y][x][NORTH] == 0 && wall[ny][nx][WEST] == 0) return 1;
		}
		else if (d == WEST) {
			if (wall[y][x][SOUTH] == 0 && wall[ny][nx][EAST] == 0) return 1;
		}
		else if (d == SOUTH) {
			if (wall[y][x][EAST] == 0 && wall[ny][nx][NORTH] == 0) return 1;
		}
		else if(d==NORTH) {
			if(wall[y][x][WEST]== 0 && wall[ny][nx][SOUTH] == 0) return 1;
		}
	}
	else {
		//우측
		if (d == EAST) {
			if (wall[y][x][SOUTH] == 0 && wall[ny][nx][WEST] == 0) return 1;
		}
		else if (d == WEST) {
			if (wall[y][x][NORTH] == 0 && wall[ny][nx][EAST] == 0) return 1;
		}
		else if (d == SOUTH) {
			if (wall[y][x][WEST] == 0 && wall[ny][nx][NORTH] == 0) return 1;
		}
		else if (d == NORTH) {
			if (wall[y][x][EAST] == 0 && wall[ny][nx][SOUTH] == 0) return 1;
		}
	}
	return 0;
}

 

4. 온도 조절 ( Adust_Temp() )

• 맵을 모두 돌면서, 사방의 온도와 자기 온도를 비교해서 조절할 양을 별도 배열에 정리해준다. (tmpmap) 
• 이때, 4방향을 모두 살폈으면 visited배열에 체크를 해서 다시 얘를 비교하지 않도록 해준다. 
• 마지막으로 tmpmap에 있는조절량을 map에 반영해준다.

void Adjust_Temp(void) {
	memset(visited, 0, sizeof(visited));
	memset(tmpmap, 0, sizeof(tmpmap));
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			visited[i][j] = 1;
			for (int k = 0; k < 4; k++) {
				int ny = i + dy[k];
				int nx = j + dx[k];
				if (ny<1 || ny>R || nx<1 || nx>C) continue;
				if (visited[ny][nx] == 1) continue;
				if (wall[i][j][k] == 1) continue;
				if (map[i][j] > map[ny][nx]) {
					int tmp = (map[i][j] - map[ny][nx]) / 4;
					tmpmap[i][j] -= tmp, tmpmap[ny][nx] += tmp;
				}
				else {
					int tmp = (map[ny][nx] - map[i][j]) / 4;
					tmpmap[ny][nx] -= tmp, tmpmap[i][j] += tmp;
				}
			}
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			map[i][j] += tmpmap[i][j];
		}
	}
}

 

5. 가에 있는 칸들 온도 내리기 ( Low_Down_Temp() )

꼭짓점이 중복되지 않도록 해준다. (그냥 이중 for문으로만 해결하지 않기!)

void Low_Down_Temp(void) {
	if (map[1][1] > 0) map[1][1]--;
	if (map[1][C] > 0) map[1][C]--;
	if (map[R][1] > 0) map[R][1]--;
	if (map[R][C] > 0) map[R][C]--;
	for (int i = 2; i < C; i++) {
		if (map[1][i] > 0) map[1][i]--;
		if (map[R][i] > 0) map[R][i]--;
	}
	for (int i = 2; i < R; i++) {
		if (map[i][1] > 0) map[i][1]--;
		if (map[i][C] > 0) map[i][C]--;
	}
}

6. 주어진 타겟 칸들의 온도 체크 ( Check_Temp() )

입력을 받을 때 target이라는 배열에 온도 체크할 칸들의 좌표를 저장해두었다가 이 배열만 순회하면서 온도 체크 해주면 된다.

int Check_Temp(void) {
	for (int i = 0; i < tcnt; i++) {
		if (map[target[i].y][target[i].x] < K) return 0;
	}
	return 1;
}

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXRC 20
#define EAST 0
#define WEST 1
#define SOUTH 2
#define NORTH 3

int R, C, K, W;
int map[MAXRC + 5][MAXRC + 5];
int visited[MAXRC + 5][MAXRC + 5];
int tmpmap[MAXRC + 5][MAXRC + 5];
int wall[MAXRC + 5][MAXRC + 5][4]; // 해당 좌표의 동서남북에 벽 유무
struct{
	int y, x, d;
}heater[MAXRC * MAXRC];
int hcnt = 0;
struct {
	int y, x;
}target[MAXRC*MAXRC];
int tcnt;

int dy[] = { 0, 0, 1, -1 }; //동서남북
int dx[] = { 1, -1, 0, 0 };

// 동서남북 바람 방향따른 퍼지는 포지션
int wdy[4][3] = { {-1, 0, 1}, {1, 0, -1}, {1, 1, 1}, {-1, -1, -1} };
int wdx[4][3] = { {1, 1, 1}, {-1, -1, -1}, {1, 0, -1}, {-1, 0, 1} };

void Get_Input(void) {
	scanf("%d %d %d", &R, &C, &K);
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] >= 1 && map[i][j] < 5) {
				// 히터이다
				if (map[i][j] == 1) map[i][j] = EAST;
				if (map[i][j] == 2) map[i][j] = WEST;
				if (map[i][j] == 3) map[i][j] = NORTH;
				if (map[i][j] == 4) map[i][j] = SOUTH;
				heater[hcnt].y = i;
				heater[hcnt].x = j;
				heater[hcnt].d = map[i][j];
				hcnt++;
				map[i][j] = 0;
			}
			else if (map[i][j] == 5) {
				target[tcnt].y = i, target[tcnt++].x = j;
				map[i][j] = 0;
			}
		}
	}
	int y, x, t;
	scanf("%d", &W);
	for (int i = 0; i < W; i++) {
		scanf("%d %d %d", &y, &x, &t);
		if (t == 0) {
			wall[y][x][NORTH] = 1;
			wall[y - 1][x][SOUTH] = 1;
		}
		else {
			wall[y][x][EAST] = 1;
			wall[y][x+1][WEST] = 1;
		}
	}
}


void Print_Map(void) {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			printf("%d", map[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}


int Check_Wall(int y, int x, int ny, int nx, int d, int i) {
	if (i == 1) {
		// 중간
		if (wall[y][x][d] == 0) return 1;
	}
	else if (i == 0) {
		// 좌측
		if (d == EAST) {
			if (wall[y][x][NORTH] == 0 && wall[ny][nx][WEST] == 0) return 1;
		}
		else if (d == WEST) {
			if (wall[y][x][SOUTH] == 0 && wall[ny][nx][EAST] == 0) return 1;
		}
		else if (d == SOUTH) {
			if (wall[y][x][EAST] == 0 && wall[ny][nx][NORTH] == 0) return 1;
		}
		else if(d==NORTH) {
			if(wall[y][x][WEST]== 0 && wall[ny][nx][SOUTH] == 0) return 1;
		}
	}
	else {
		//우측
		if (d == EAST) {
			if (wall[y][x][SOUTH] == 0 && wall[ny][nx][WEST] == 0) return 1;
		}
		else if (d == WEST) {
			if (wall[y][x][NORTH] == 0 && wall[ny][nx][EAST] == 0) return 1;
		}
		else if (d == SOUTH) {
			if (wall[y][x][WEST] == 0 && wall[ny][nx][NORTH] == 0) return 1;
		}
		else if (d == NORTH) {
			if (wall[y][x][EAST] == 0 && wall[ny][nx][SOUTH] == 0) return 1;
		}
	}
	return 0;
}


typedef struct e {
	int y, x, h;
}ELE;
ELE q[MAXRC * MAXRC * 10];
int wp, rp;
void enq(int y, int x, int h) { q[wp].y = y, q[wp].x = x, q[wp++].h = h; }
ELE deq(void) { return q[rp++]; }
int empty(void) { return rp == wp; }

void BFS(int sy, int sx, int d) {
	memset(visited, 0, sizeof(visited));
	wp = rp = 0;
	
	sy += dy[d];
	sx += dx[d];
	if (sy < 1 || sy > R || sx< 1 || sx > C) return;
	enq(sy, sx, 5);
	visited[sy][sx] = 1;
	map[sy][sx] += 5;
	
	while (!empty()) {
		ELE cur = deq();
		for (int i = 0; i < 3; i++) {
			int ny = cur.y + wdy[d][i];
			int nx = cur.x + wdx[d][i];
			if (ny<1 || ny>R || nx<1 || nx>C) continue;
			if (visited[ny][nx]) continue;
			if (!Check_Wall(cur.y, cur.x, ny, nx, d, i)) continue;
			visited[ny][nx] = 1;
			map[ny][nx] += cur.h - 1;
			if (cur.h - 1 == 1) continue; // 이거 잊음!!!
			enq(ny, nx, cur.h - 1);
		}
	}
}

void Wind_Blows(void) {
	for (int i = 0; i < hcnt; i++) {
		BFS(heater[i].y, heater[i].x, heater[i].d);
		//Print_Map();
	}
}

void Adjust_Temp(void) {
	memset(visited, 0, sizeof(visited));
	memset(tmpmap, 0, sizeof(tmpmap));
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			visited[i][j] = 1;
			for (int k = 0; k < 4; k++) {
				int ny = i + dy[k];
				int nx = j + dx[k];
				if (ny<1 || ny>R || nx<1 || nx>C) continue;
				if (visited[ny][nx] == 1) continue;
				if (wall[i][j][k] == 1) continue;
				if (map[i][j] > map[ny][nx]) {
					int tmp = (map[i][j] - map[ny][nx]) / 4;
					tmpmap[i][j] -= tmp, tmpmap[ny][nx] += tmp;
				}
				else {
					int tmp = (map[ny][nx] - map[i][j]) / 4;
					tmpmap[ny][nx] -= tmp, tmpmap[i][j] += tmp;
				}
			}
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			map[i][j] += tmpmap[i][j];
		}
	}
}

void Low_Down_Temp(void) {
	if (map[1][1] > 0) map[1][1]--;
	if (map[1][C] > 0) map[1][C]--;
	if (map[R][1] > 0) map[R][1]--;
	if (map[R][C] > 0) map[R][C]--;
	for (int i = 2; i < C; i++) {
		if (map[1][i] > 0) map[1][i]--;
		if (map[R][i] > 0) map[R][i]--;
	}
	for (int i = 2; i < R; i++) {
		if (map[i][1] > 0) map[i][1]--;
		if (map[i][C] > 0) map[i][C]--;
	}
}

int Check_Temp(void) {
	for (int i = 0; i < tcnt; i++) {
		if (map[target[i].y][target[i].x] < K) return 0;
	}
	return 1;
}

int main(void) {
	Get_Input();
	int choco = 0;
	while (1) {
		if (choco > 100) break;
		Wind_Blows();
		Adjust_Temp();
		//Print_Map();
		Low_Down_Temp();
		//Print_Map();
		choco++;
		if (Check_Temp()) break;
	}
	printf("%d", choco);
	return 0;
}