[아이디어]
중간에 삽질하느라 디버깅하는데 오래 걸리기도 하고,
지시문 #define에 대해서...
[들어가기 전] #define R_MAX 20 + 1 ~~~ int wall[R_MAX * 2][R_MAX * 2] 위 코드에서 R_MAX * 2는 어떤 정수일까요? 1. 42 2. 22 정답을 아시는 분은 뒤로 가셔도 좋습니다! ㅎㅎ 정답은 2번 입니다! 왜 이런 결과가 나
kansstory.tistory.com
복잡했지만 단순 구현 문제였습니다.
단지 BFS를 이용해
인접한 네 방향을 주로 탐색했다면,
한 쪽 방향으로 퍼지게끔
구현에 변형이 필요했습니다.
또한 각 칸 사이엔 벽이 존재할 수 있는데
벽의 정보는
map의 크기를 2배로 늘려
사이사이 벽의 위치에 대한 좌표를 구할 수 있게끔 설계했습니다.
[요약]
1. 온풍기에서 바람이 퍼지듯이 불고
2. 온도를 조절하며
3. 최외곽의 온도가 1이상이라면 1씩 감소시키고
4. 초콜릿을 드시면
됩니다.
[방법]
바람이 한 방향으로 퍼지면서 나아간다.
이 부분은 BFS탐색 기법을 활용해 구현했습니다.
저는 방향벡터로
int dy[5] = { 0,0,0,-1,1 }; // 동 서 북 남
int dx[5] = { 0,1,-1,0,0 };
를 사용했습니다.
위 그림처럼 온풍기의 바람 방향이 동쪽(1)일 때,
방향벡터 배열 1~4까지 탐색하면서
① 동쪽(1)일 때,
동쪽(1) 방향으로 벽의 유무를 확인한 뒤
벽이 없다면 이동하고
② 서쪽(2)은 지나치고
③ 북쪽(3)이나 남쪽(4)일 때,
위, 아래에 벽의 유무를 확인한 뒤
벽이 없다면 이동하고
동쪽(1)의 벽의 유무를 확인한 뒤
벽이 없다면 이동하도록
구현했습니다.
벽 위치 저장
map배열 좌표에 근거해
(r, c, d) = {(5, 4, 0), (4, 4, 1), (5, 6, 0)}
입력을 받는다면,
벽의 위치는 wall배열에 따르면
(r, c) = {(8, 7), (7,8), (8,11)}
에 저장되어 있게 됩니다.
따라서,
map배열에서 r좌표가 x이라면
wall배열에서 r좌표는 (x * 2) -1 임이 성립됩니다.
map배열 좌표에서 r좌표가 x, x+1인
사이의 벽은
wall배열에서 (x * 2)임이 성립됩니다.
이를 가정하고 wall 배열을 생성시,
map 배열 크기의 2배만큼 키워
벽의 좌표를 저장했습니다.
[설명]
blow_from_heater(온풍기 인덱스)
주사위를 이동시켰을 때,
주사위의 좌표, 방향, 전개도, 획득한 점수 등을
업데이트해주는 함수
void blow_from_heater(int num) {
/*
온풍기에서 바람이 분다.
*/
queue<pair<int, int>> q; // 탐색할 좌표를 순서대로 집어 넣음
int heater_map[R_MAX][C_MAX] = { 0, }; // 바람이 불면서 몇도의 온도가 저장되는지 기록
int used[R_MAX][C_MAX] = { 0, }; // 이미 바람이 지나갔는지 확인
NODE* now_heater = &heater[num]; // heater배열에서 현재 온풍기에 대한 정보를 저장해둠
// 온풍기에서 바람이 불기 시작하는 위치
int sy = now_heater->y + dy[now_heater->d];
int sx = now_heater->x + dx[now_heater->d];
heater_map[sy][sx] = 5;
used[sy][sx] = 1;
q.push(make_pair(sy, sx));
while (!q.empty()) {
pair<int, int> now = q.front();
q.pop();
FOR(i, 1, 5) {
if (now_heater->d == 1 && i == 2) continue; // 온풍기 방향이 동쪽이면 서쪽은 탐색안함
else if (now_heater->d == 2 && i == 1) continue; // 온풍기 방향이 서쪽이면 동쪽은 탐색안함
else if (now_heater->d == 3 && i == 4) continue; // 온풍기 방향이 북쪽이면 남쪽은 탐색안함
else if (now_heater->d == 4 && i == 3) continue; // 온풍기 방향이 남쪽이면 북쪽은 탐색안함
// 현재 위치에 대한 벽의 유무를 파악
int ty = (now.first * 2) - 1 + dy[i];
int tx = (now.second * 2) - 1 + dx[i];
if (ty < 1 || ty >((R * 2) - 1) || tx < 1 || tx >((C * 2) - 1)) continue; // 범위를 벗어난 벽을 탐색하지 않는지 확인
if (wall[ty][tx] == 1) continue; // 벽에 막혔다면 탐색안함
// 다음 바람이 불 다음 위치 업데이트
int ny = now.first + dy[i];
int nx = now.second + dx[i];
if (i != now_heater->d) {
/*
북쪽이나 남쪽이라면 바람이 불던 방향(동 or 서)으로 한번더 꺽어줘야함
동쪽이나 서쪽이라면 바람이 불던 방향(북 or 남)으로 한번더 꺽어줘야함
*/
// 현재 위치에 대한 벽의 유무파악
ty = (ny * 2) - 1 + dy[now_heater->d];
tx = (nx * 2) - 1 + dx[now_heater->d];
if (ty < 1 || ty >((R * 2) - 1) || tx < 1 || tx >((C * 2) - 1)) continue; // 범위를 벗어난 벽을 탐색하지 않는지 확인
if (wall[ty][tx] == 1) continue; // 벽에 막혔다면
// 다음 바람이 불 다음 위치 업데이트
ny = ny + dy[now_heater->d];
nx = nx + dx[now_heater->d];
}
if (ny < 1 || ny > R || nx < 1 || nx > C) continue; //맵 밖으로 바람이 불진 않는지 확인
if (heater_map[ny][nx] != 0) continue; // 이미 바람이 불었던 위치가 아닌지 확인
if (used[ny][nx] != 0) continue; // 이미 바람이 불었던 위치가 아닌지 확인
if ((heater_map[now.first][now.second] - 1) < 1) continue; // 온도가 0이하라면 더이상 바람이 닿지 않음
heater_map[ny][nx] = heater_map[now.first][now.second] - 1; // 다음 바람이 불 위치의 온도를 저장
used[ny][nx] = 1; // 바람이 지나간 자리임을 표시
q.push(make_pair(ny, nx));
}
}
add_heaterMap_to_temper(heater_map);
}
add_heaterMap_to_temper(int heater_map[][C_MAX])
전체 온도를 기록해둔 temper맵에
온풍기에서 바람이 나온 상태의 온도를 기록해둔 heater_map맵의 값만큼
더해줌
void add_heaterMap_to_temper(int heater_map[][C_MAX]) {
FOR(y, 1, R + 1) {
FOR(x, 1, C + 1) {
temper[y][x] += heater_map[y][x];
}
}
}
control_temper()
주위 온도를 살펴보며 온도를 조절해줌
void control_temper() {
/*
온도 조절
*/
int spread_temper[R_MAX][C_MAX] = { 0, }; // 온도 조절하기 위해 주변으로 퍼진 온도 값 저장
int flow_out_temper[R_MAX][C_MAX] = { 0, }; // 온도 조절하기 위해 주변으로 퍼지기 위해 빠져나간 온도 값 저장
FOR(y, 1, R + 1) {
FOR(x, 1, C + 1) {
spread_temper[y][x] = 0;
flow_out_temper[y][x] = 0;
}
}
FOR(y, 1, (R + 1)) {
FOR(x, 1, (C + 1)) {
if (temper[y][x] != 0) {
FOR(i, 1, 5) {
// 벽의 유무 확인
int ty = (y * 2) - 1 + dy[i];
int tx = (x * 2) - 1 + dx[i];
if (ty < 1 || ty >((R * 2) - 1) || tx < 1 || tx >((C * 2) - 1)) continue;
if (wall[ty][tx] == 1) continue;
// 온도가 빠져나갈 좌표 확인
int ny = y + dy[i];
int nx = x + dx[i];
if (ny<1 || ny > R || nx < 1 || nx > C) continue;
if (temper[y][x] > temper[ny][nx]) {
int L = (temper[y][x] - temper[ny][nx]) >> 2; // (두칸의 온도차 / 4)
spread_temper[ny][nx] += L;
flow_out_temper[y][x] -= L;
}
}
flow_out_temper[y][x] += temper[y][x];
}
}
}
FOR(y, 1, (R + 1)) {
FOR(x, 1, (C + 1)) {
temper[y][x] = flow_out_temper[y][x] + spread_temper[y][x];
}
}
}
decrease_outside_temper()
최외곽 좌표에 온도가 1이상이면 1씩 감소
void decrease_outside_temper() {
/*
가장 바깥쪽 칸의 온도 1씩 감소
*/
FOR(x, 1, C) {
if (temper[1][x] >= 1) {
temper[1][x] -= 1;
}
}
FOR(x, 2, (C + 1)) {
if (temper[R][x] >= 1) {
temper[R][x] -= 1;
}
}
FOR(y, 2, (R + 1)) {
if (temper[y][1] >= 1) {
temper[y][1] -= 1;
}
}
FOR(y, 1, R) {
if (temper[y][C] >= 1) {
temper[y][C] -= 1;
}
}
}
eat_chocolate()
초콜릿 먹기
void eat_chocolate() {
/* 초콜릿 먹기 */
++chocolate;
}
isReachTargetTemper()
조사할 위치가 목표 온도에 도달했는지
bool isReachTargetTemper() {
/* 목표 온도에 도달 했는지 */
FOR(i, 0, t_cnt) {
if (temper[target[i].y][target[i].x] < K) {
return false;
}
}
return true;
}
[코드]
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define R_MAX (20 + 1)
#define C_MAX (20 + 1)
#define WALL_MAX 21
#define FOR(i,s,e) for(int i=s; i<e; ++i)
int R, C, K;
int map[R_MAX][C_MAX];
struct NODE {
int y;
int x;
int d;
};
NODE heater[410];
NODE target[410];
int dy[5] = { 0,0,0,-1,1 }; // 동 서 북 남
int dx[5] = { 0,1,-1,0,0 };
int W;
int wall[R_MAX * 2][C_MAX * 2];
int temper[R_MAX][C_MAX];
int h_cnt;
int t_cnt;
int chocolate;
void add_heaterMap_to_temper(int heater_map[][C_MAX]) {
FOR(y, 1, R + 1) {
FOR(x, 1, C + 1) {
temper[y][x] += heater_map[y][x];
}
}
}
void blow_from_heater(int num) {
/*
온풍기에서 바람이 분다.
*/
queue<pair<int, int>> q;
int heater_map[R_MAX][C_MAX] = { 0, };
int used[R_MAX][C_MAX] = { 0, };
NODE* now_heater = &heater[num];
int sy = now_heater->y + dy[now_heater->d];
int sx = now_heater->x + dx[now_heater->d];
heater_map[sy][sx] = 5;
used[sy][sx] = 1;
q.push(make_pair(sy, sx));
while (!q.empty()) {
pair<int, int> now = q.front();
q.pop();
FOR(i, 1, 5) {
if (now_heater->d == 1 && i == 2) continue;
else if (now_heater->d == 2 && i == 1) continue;
else if (now_heater->d == 3 && i == 4) continue;
else if (now_heater->d == 4 && i == 3) continue;
int ty = (now.first * 2) - 1 + dy[i];
int tx = (now.second * 2) - 1 + dx[i];
if (ty < 1 || ty >((R * 2) - 1) || tx < 1 || tx >((C * 2) - 1)) continue;
if (wall[ty][tx] == 1) continue; // 벽에 막혔다면
int ny = now.first + dy[i];
int nx = now.second + dx[i];
if (i != now_heater->d) {
ty = (ny * 2) - 1 + dy[now_heater->d];
tx = (nx * 2) - 1 + dx[now_heater->d];
if (ty < 1 || ty >((R * 2) - 1) || tx < 1 || tx >((C * 2) - 1)) continue;
if (wall[ty][tx] == 1) continue; // 벽에 막혔다면
ny = ny + dy[now_heater->d];
nx = nx + dx[now_heater->d];
}
if (ny < 1 || ny > R || nx < 1 || nx > C) continue;
if (heater_map[ny][nx] != 0) continue;
if (used[ny][nx] != 0) continue;
if ((heater_map[now.first][now.second] - 1) < 1) continue;
heater_map[ny][nx] = heater_map[now.first][now.second] - 1;
used[ny][nx] = 1;
q.push(make_pair(ny, nx));
}
}
add_heaterMap_to_temper(heater_map);
}
void control_temper() {
/*
온도 조절
*/
int spread_temper[R_MAX][C_MAX] = { 0, };
int flow_out_temper[R_MAX][C_MAX] = { 0, };
FOR(y, 1, R + 1) {
FOR(x, 1, C + 1) {
spread_temper[y][x] = 0;
flow_out_temper[y][x] = 0;
}
}
FOR(y, 1, (R + 1)) {
FOR(x, 1, (C + 1)) {
if (temper[y][x] != 0) {
FOR(i, 1, 5) {
int ty = (y * 2) - 1 + dy[i];
int tx = (x * 2) - 1 + dx[i];
if (ty < 1 || ty >((R * 2) - 1) || tx < 1 || tx >((C * 2) - 1)) continue;
if (wall[ty][tx] == 1) continue;
int ny = y + dy[i];
int nx = x + dx[i];
if (ny<1 || ny > R || nx < 1 || nx > C) continue;
if (temper[y][x] > temper[ny][nx]) {
int L = (temper[y][x] - temper[ny][nx]) >> 2; // (두칸의 온도차 / 4)
spread_temper[ny][nx] += L;
flow_out_temper[y][x] -= L;
}
}
flow_out_temper[y][x] += temper[y][x];
}
}
}
FOR(y, 1, (R + 1)) {
FOR(x, 1, (C + 1)) {
temper[y][x] = flow_out_temper[y][x] + spread_temper[y][x];
}
}
}
void decrease_outside_temper() {
/*
가장 바깥쪽 칸의 온도 1씩 감소
*/
FOR(x, 1, C) {
if (temper[1][x] >= 1) {
temper[1][x] -= 1;
}
}
FOR(x, 2, (C + 1)) {
if (temper[R][x] >= 1) {
temper[R][x] -= 1;
}
}
FOR(y, 2, (R + 1)) {
if (temper[y][1] >= 1) {
temper[y][1] -= 1;
}
}
FOR(y, 1, R) {
if (temper[y][C] >= 1) {
temper[y][C] -= 1;
}
}
}
void eat_chocolate() {
/* 초콜릿 먹기 */
++chocolate;
}
bool isReachTargetTemper() {
/* 목표 온도에 도달 했는지 */
FOR(i, 0, t_cnt) {
if (temper[target[i].y][target[i].x] < K) {
return false;
}
}
return true;
}
void sol() {
while (isReachTargetTemper() == false) {
FOR(i, 0, h_cnt) {
blow_from_heater(i);
}
control_temper();
decrease_outside_temper();
eat_chocolate();
if (chocolate > 100) {
chocolate = 101;
break;
}
}
cout << chocolate;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
cin >> R >> C >> K;
FOR(y, 1, (R + 1)) {
FOR(x, 1, (C + 1)) {
cin >> map[y][x];
if (map[y][x] == 5) {
target[t_cnt].y = y;
target[t_cnt++].x = x;
}
else if (map[y][x] != 0) {
heater[h_cnt].y = y;
heater[h_cnt].x = x;
heater[h_cnt++].d = map[y][x];
}
}
}
cin >> W;
FOR(i, 0, W) {
int r = 0, c = 0, d = 0;
cin >> r >> c >> d;
int y = (r * 2) - 1;
int x = (c * 2) - 1;
if (d == 0) {
wall[y - 1][x] = 1;
}
else if (d == 1) {
wall[y][x + 1] = 1;
}
}
sol();
return 0;
}
[문제 출처]
반응형
'Problem Solving > 백준' 카테고리의 다른 글
| [백준_23288] 주사위 굴리기 2 (C++) (4) | 2024.01.29 |
|---|
