백준 18405 C++
경쟁적 전염 성공
|
|
|
시간 제한
|
메모리 제한
|
제출
|
정답
|
맞힌 사람
|
정답 비율
|
|
1 초
|
256 MB
|
16623
|
5236
|
3427
|
29.271%
|
문제
NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.
시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.
예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.
1초가 지난 후에 시험관의 상태는 다음과 같다.
2초가 지난 후에 시험관의 상태는 다음과 같다.
결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.
입력
첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)
출력
S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.
예제 입력 1
|
3 3 1 0 2 0 0 0 3 0 0 2 3 2
|
예제 출력 1
|
3
|
예제 입력 2
|
3 3 1 0 2 0 0 0 3 0 0 1 2 2
|
접근
문제를 읽어보면서, 키워드가 여러가지 있었다. 일단 가장 먼저 BFS를 사용하는 것을 직감 했다. 왜냐면 초마다 바이러스들이 전염 되는데, 상하좌우로 이동하면서 깊게 내려가는게 아닌 영역별로 넘어가기 때문이다.
두 번째로, 낮은 수의 바이러스가 먼저 칸을 차지 할 수 있다는 내용에 집중했다. 상대적으로 번호가 작은 바이러스가 먼저 퍼저나가겠구나. 라고 생각했다. 낮은 번호에 대해 먼저 퍼져나가는 것. 이 방법에 대해 고민을 하면서 두 가지를 고민했다.
첫 번째는 정렬(sort)이다. 정렬은 코드가 눈에 보이고 직관적이라고 생각해서 사용하기 편하다고 생각했다. 그리고 무엇보다 자주 사용해 봐서 하기 편하다고 생각했다.
두 번째는 우선순위 큐(priority queue)이다. 우선순위 큐를 생각 한 이유는 일단 BFS가 주로 큐를 활용하여 구현 되기 때문이다. 낮은 수에 대해서 우선순위를 부여하는 방식으로 생각했다.
그러나 문제의 특성을 잘 살펴야 했다. 우선순위 큐의 경우에는 큐에 값이 들어올 때"마다" 우선순위에 따라 정렬을 한다. 문제에는 하루에 1, 2, 3, ...번 바이러스가 돌아가야 한다. 예제 케이스에서 1일째에는 1번, 2번, 3번 순서로 진행되어야 하고, 2일째에는 1일째의 1번 바이러스의 결과, 1일째의 2번 바이러스의 결과, 1일째의 3번 바이러스의 결과 순서대로 돌아가야 한다.
일단 우선순위 큐를 사용하면 1번 바이러스를 돌렸을 때, 1일째의 1번 바이러스의 결과가 그대로 다음 순서가 되어버린다. 1번을 BFS돌리면 2번으로 넘어가는 것이 아닌 방금 돌아간 1번의 결과인 1번 바이러스에서 BFS가 돌아가게 되는 것이다.
그렇다면 정렬은 어떨까? 1일째에 1번, 2번, 3번이 돌아가고 2일째에도 1번, 2번, 3번이 돌아가게 만들어야 한다면 정렬을 한 후. 1일차 BFS 를 돌리고 그 결과를 다시 정렬한 후 2일차 BFS를 돌리는 방법이 직관적일 것이다. 물론 맞긴 하다. 그런데 굳이 매일마다 정렬을 할필요가 있을까? 이미 1일차에 정렬을 했다면, 1번 부터 차례대로 큐에 들어올 것이다 (1일차 1번 바이러스를 BFS돌렸을 때 : 2, 3.....1`, 1`...) 그러므로, 정렬을 맨처음만 한다면 굳이 매일 정렬을 해줄 필요가 없다.
그러므로, 맨 처음 값을 받았을 때만 정렬하면 그 이후로는 알아서 순차적으로 진행될 것이다.
문제를 풀면서 생각한 고려사항들은 N * N 정사각형 모양의 map이고, 일반적으로 생각하는 x, y축이 바뀌어 있었다. (사실 x, y축 바뀌어 있어서 고생 좀 했다.)
코드 풀이
일단 큐를 사용하지 않았다. 벡터를 사용해 이중 pair로 여러번 묶었다. virus vector에는 차례대로 <바이러스 번호, <y축 좌표, x축 좌표>>가 들어가 있다. 다른 분의 코드를 참고 하였다.
- 입력 코드
cin >> N >> K;
vector<pair<int, pair<int, int>>> virus;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> map[i][j];
if (map[i][j] != 0)
{
virus.push_back({map[i][j], {i, j}});
check[i][j] = 1;
}
else
{
check[i][j] = 0;
}
}
}
cin >> S >> Y >> X;map을 입력 받으면서 동시에 check에도 표시해준다. 존재한다면 1로, 존재 하지 않는다면 0을 넣는다. 다만, map에 virus가 존재하는 상태라면, virus 벡터에 바이러스 번호에 관한 정보(map[i][j])와 위치 {i, j}를 넣어준다.
- 정렬
sort(virus.begin(), virus.end());virus 벡터를 바이러스의 번호에 맞게 정렬을 시켜준다. pair 때문에 헷갈릴수도 있는데, vector<바이러스 번호<x, y>> 에 의해 바이러스 번호에 맞게 정렬을 하게 된다.
- 핵심 로직
int cur_time = 0;
while (cur_time < S) // 초마다 while문을 돌리게 된다.
{
int vircount = virus.size();
//virus 벡터의 크기만큼 돌려준다. virus에는 바이러스가 존재하는 칸만 바이러스 정보와 함께 들어있다.
for (int i = 0; i < vircount; i++)
{
int cur_vir = virus[i].first;
int cur_y = virus[i].second.first; //현재 y좌표.
int cur_x = virus[i].second.second; //현재 x좌표.
for (int j = 0; j < 4; j++)
{
int ny = cur_y + dy[j];
int nx = cur_x + dx[j];
if (check[ny][nx])
{
continue; //방문한 적 있는 좌표면 continue.
}
if (1 > ny || ny > N || 1 > nx || nx > N)
{
continue; // 범위 밖일 경우 continue
}
map[ny][nx] = cur_vir; //map에 현 바이러스의 정보를 넣어준다.
virus.push_back({cur_vir, {ny, nx}}); //virus에 pushback해준다.
}
}
if (map[Y][X])
{
break; // 바이러스가 이미 채워졌다면, while문을 나와서 바로 map[Y][X]를 반환한다.
}
cur_time++;
}pair을 겹쳐 쓰다 보니 cur_y, cur_x 변수가 저런식으로 나오게 되었다.ㅋㅋㅋㅋㅋㅋㅋ
일단 while문은 현재 시간(cur_time)이 S를 넘지 않을때로 했다. vircount의 경우에는 virus 벡터 안에 있는 정보만큼 돌려준다.
예제의 경우로 미루어 볼 때,
가장 먼저, 현재 시간은 0초로 설정 되어있다. 그렇다면 맵과 바이러스의 상태는 이렇게 될 것이다.
이후, 메인코드를 실행하면 virus 벡터에는
<1, <0, 0>>, <2, <0, 2>>, <3, <2, 0>>, <1, <0, 1>>, <1, <1, 0>>, <2, <1, 2>>, <3, <2, 1>>
이렇게 들어간다
뒤는 귀찮아서 생략...이런식으로 쭉쭉 진행한다.
전체 코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int N, K, S, X, Y;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
int map[201][201];
bool check[201][201];
int main()
{
cin >> N >> K;
vector<pair<int, pair<int, int>>> virus;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> map[i][j];
if (map[i][j] != 0)
{
virus.push_back({map[i][j], {i, j}});
check[i][j] = 1;
}
else
{
check[i][j] = 0;
}
}
}
cin >> S >> Y >> X;
sort(virus.begin(), virus.end());
int cur_time = 0;
while (cur_time < S)
{
int vircount = virus.size();
for (int i = 0; i < vircount; i++)
{
int cur_vir = virus[i].first;
int cur_y = virus[i].second.first;
int cur_x = virus[i].second.second;
for (int j = 0; j < 4; j++)
{
int ny = cur_y + dy[j];
int nx = cur_x + dx[j];
if (check[ny][nx])
{
continue;
}
if (1 > ny || ny > N || 1 > nx || nx > N)
{
continue;
}
map[ny][nx] = cur_vir;
virus.push_back({cur_vir, {ny, nx}});
}
}
if (map[Y][X])
{
break;
}
cur_time++;
}
cout << map[Y][X] << "\n";
}느낀 점
정렬이냐 우선순위큐이냐 고민을 좀 많이 했다.
그 외엔 정렬이 들어간 bfs라 사실 많이 고민은 안했는데 사실 아쉬웠던 점은 큐로 하지 않았고 벡터로 해서 while문을 한번 돌릴 때마다 벡터 전체를 한번씩 다시 읽히는 비효율 적인 알고리즘을 짰다. 허허. 그냥 이런 방식도 있구나~ 하면서 본거라 큐 안썼지만...