[백준 / #14502 / C++] 연구소

 

이번 문제도 뭔가 척 보면 알 수 있을 문제이지만 나는 시간을 너무 줄이려고 욕심을 부리다보니 한참을 돌아갔던 문제

 

이다.

 

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

14502번: 연구소

 

문제해석:

 

 

문제에서 주어진 자료형의 최대 사이즈가 굉장히 작다는 것을 알 수 있다. N, M이 8보다 작거나 같으므로 2차원 배열을 만

 

들고 모두 탐색해도 8 x 8 = 64로 굉장히 작은 것을 볼 수 있다. 그렇다면 여기서 브루트포스(brute-force) 즉 전수조사를

 

하면 된다는 것을 눈치 챌 수 있다. 게다가 바이러스가 퍼지는 형태는 전에 문제들에서 다뤘던 너비우선탐색(BFS)을 사용

 

하면 쉽게 구할 수 있다. 물론 깊이우선탐색(DFS)을 사용해도 문제가 풀릴 것이지만 나는 너비우선탐색을 사용하여 문제

 

를 해결했다. 바이러스는 앞 뒤 양 옆으로 퍼질 수 있고 만약 1인 벽이 있다면 바이러스는 그 쪽으로는 퍼질 수 없다. 미로

 

탐색 문제와 굉장히 흡사하며 토마토 문제처럼 동시성은 없다. 또한 이 문제를 풀다가 보면 여러번 모든 경우의 수를 계산

 

해야 하므로 기존에 문제에서 주어진 연구소 지도를 복사한 새로운 배열에 벽을 3개 세우고 계산하며 반복해줘야 한다. 즉

 

algorithm 헤더 파일의 copy(&arr[][], &arr[][] + n * m, &copy[][])를 해줘야 한다. (간략하게 표현했음)

 

 

 

알고리즘 해설 및 코드:

 

 

코드를 살펴보자.

 

 

토마토 문제와 마찬가지로 연구소 지도를 입력받으면서 바이러스의 위치와 통로에 대한 정보를 각각의 큐와 벡터에 저장

 

해주었다. 이 때 반복적인 연산을 해야하므로 바이러스의 위치에 대한 큐가 만약 한 연산에 대해 사용된다면 돌아올 수 없

 

으므로 save 벡터를 만들어줘서 같이 저장해두고 연산을 반복할 때마다 save벡터에서 끌어다가 사용해 초기화시켜줬다.

 

 

통로의 정보를 미리 저장해준 이유는 그나마 조금이라도 연산 시간을 줄이기 위함도 있고 통로의 정보를 저장하지 않으면

 

내가 설계한 알고리즘은 x와 y좌표(행과 열)를 모두 사용하기 때문에 6중 for문이라는 아주 극악무도한 코드가 완성된다.

 

따라서 하나의 pair를 품은 벡터에 저장함으로써 6중 for문을 방지하고자 저장하였다.

 

 

이제 이렇게 저장을 했으면 통로 정보를 저장한 벡터에서 세개씩 차례대로 벽을 세운 뒤 바이러스가 모두 퍼졌을 때 살 수

 

있는 공간들을 계산해준다. 바이러스가 퍼지는 경우는 앞에서 말했듯이 너비우선탐색(BFS)를 이용해 계산하고 마지막에

 

는 살아 있는 공간들의 개수를 세어준다. 이렇게 한 연산이 끝나면 바이러스의 위치가 담긴 큐가 비어있으므로 입력받으며

 

저장해두었던 save벡터에서 꺼내어 다시 넣어준다. 이런 연산을 수행 할 때 주의할 점이 계속해서 연산을 실행할 때 연구

 

소 지도의 원본 데이터인 lab 배열에 벽을 세워주고 바이러스 연산을 실행한다면 이렇게 바이러스가 퍼진 곳과 벽을 세웠

 

던 곳을 역순으로 돌아가며 초기화시켜줘야한다. 이는 번거롭기 때문에 temp라는 임시 배열을 만들어 복사시켜주고 이

 

temp 배열에서 연산을 실행하도록 한다. 이 때 algortihm 헤더파일의 copy를 사용한다. 그렇게 매 반복 연산마다 temp 배열

 

을 만들어주고 연산을 하면 초기화의 문제도 없이 깔끔하게 돌아가고 만약 더 많은 공간이 살아 남을 수 있다면 그 수를 저

 

장해두고 비교 연산을 통해 최댓값을 구한다.

 

 

이번 문제를 통해 또 한가지 깨달은 점이 때로는 브루트 포스(brute-force)를 사용해야 할 때도 있다는 것과 반복해서 같은

 

연산을 실행한다면 초기화에 대한 문제도 한 번쯤은 생각해봐야 한다는 것이다.