문제 링크 : https://www.acmicpc.net/problem/16946
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이
www.acmicpc.net
이 문제는 다음과 같은 방법으로 접근할 경우 시간초과를 겪게된다.
배열의 값이 1인 경우, 해당 위치를 기준으로 4방위의 값이 0인 곳에서 DFS / BFS를 진행해 이동할 수 있는 칸의 갯수를 센다.
시간 제한은 2초인데, 1000*1000배열을 하나하나 BFS / DFS로 파고들었다가는 시간초과가 날 수 밖에 없다.
때문에 이 문제는 좀더 거시적인 관점에서 바라보아야 해결책이 나오는데, 방법은 다음과 같다.
1. 값이 0인 구역을 그룹화 = 라벨링 한다.
2. 같은 그룹 = 라벨의 영역은 해당 영역의 총합의 값을 모두 갖게 된다.
예를들어 그림으로 표현한다면 다음과 같다.
여기서 중요한 점은 라벨링, 즉, 그룹화이다.
만약 그룹화를 해주지 않고 그저 총합의 값들만 동일하게 나누게 된다면 아래와 붉은색으로 표시된 영역을 합산하는 과정에서 문제를 겪게 된다.
파랑색 1을 중심으로 왼쪽 0의 영역 3, 위쪽 0의 영역 3을 중복으로 합산할 수 있기 때문이다.
문제 풀이는 다음과 같다.
1. 값은 문자형으로 입력된다. 계산을 편하게 하기 위해 문자형으로 입력된 값은 int형으로 저장한다.
cin >> n >> m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin >> temp;
v[i][j] = temp-'0';
}
}2. 2중 for문을 돌려서 만약 배열의 값이 0이고 아직 방문한 적이 없다면 bfs를 진행한다.
이때 bfs함수의 매개변수는 위치값과 label 넘버다.
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(v[i][j]==0&&!ch[i][j]) bfs(i,j,num++);
}
}3. 다음은 bfs함수의 내부이다. 간략하게 훑어보고 아래 설명을 디테일하게 읽어보자.
void bfs(int a, int b, int labeling){
queue<pair<int,int>> q1; // 1
queue<pair<int,int>> q2;
cnt = 1; // 2
label[a][b] = labeling; // 3
q1.push({a,b}); // 4
q2.push({a,b});
ch[a][b] = true;
while(!q1.empty()){ // 5
y = q1.front().first;
x = q1.front().second;
q1.pop();
for(int i=0; i<4; i++){ // 6
ny = y+my[i];
nx = x+mx[i];
if(ny>=1&&ny<=n&&nx>=1&&nx<=m&&!ch[ny][nx]&&v[ny][nx]==0){ // 7
ch[ny][nx] = true; // 8
cnt++;
label[ny][nx] = labeling;
q1.push({ny,nx});
q2.push({ny,nx});
}
}
}
while(!q2.empty()){ // 9
y = q2.front().first;
x = q2.front().second;
q2.pop();
v[y][x] = cnt;
}
}(1) q1은 '0'으로 이루어진 영역값을 합산할 큐이고, q2는 합산한 영역을 해당 위치에 저장해줄 큐이다.
(2) 영역값은 1부터 증가한다.
(3) 현재 매개변수로 입력받은 위치값을 라벨링 해준다. (라벨링은 1부터 시작해서 점점 증가한다.)
(4) q1과 q2에 위치를 저장한다.
(5) q1이 빌때까지 while문을 진행한다.
(6) 현재 q1에 저장된 front값을 기준으로 4방위로 for문을 진행한다.
(7) 만약 4방위로 탐색한 지점이 탐색 가능 범위를 넘지 않았으며, 아직 방문하지 않았고 (= !ch[ny][nx]), 동시에 그 위치값이 0이라면
(8) 해당 위치를 방문했다고 표시해준다. 동시에 cnt값을 +1 해주고 해당 위치를 라벨링 해준다. 마지막으로 q1과 q2에 해당 위치값을 삽입한다.
(9) q2에 저장된 그룹핑(=라벨링)된 위치값들을 모두 합산된 영역값으로 저장해준다.
4. 그룹핑(=라벨링)을 끝맞쳤다면 이제 벽을 부수고 갈 수 있는 영역들을 계산해준다.
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(!ch[i][j]){ //1. 방문하지 않은 곳 = 벽
vector<int> arr; // 2
cnt = 1; // 3
for(int x=0; x<4; x++){ // 4
bool visited = false;
ny = i+my[x];
nx = j+mx[x];
if(ny>=1&&ny<=n&&nx>=1&&nx<=m&&ch[ny][nx]){
for(int z=0; z<arr.size(); z++){ // 5
if(arr[z]==label[ny][nx]) visited = true;
}
if(!visited){ // 6
arr.push_back(label[ny][nx]);
cnt += v[ny][nx];
}
}
}
v[i][j] = cnt%10; // 7
}
}
}(1) 2중 for문을 돌려 아직 방문하지 않은 곳, 즉, 벽일 경우에 if조건절을 진행한다.
(2) arr벡터는 중복된 라벨링들을 구별하기 위해 세운 변수이다.
(3) 벽을 부순 자리 또한 지나갈 수 있는 자리이므로, 지나갈 수 있는 장소의 갯수(=cnt)는 1부터 시작한다.
(4) 현재 지점을 기준으로 4방위로 for문을 돌린다. 만약 4방위의 지점을 방문한 적이 있다면 (=영토가 0인 지역들이 그룹핑 된 구역)
(5) 벡터 arr의 사이즈만큼 for문을 돌린다. 이 arr 벡터는 영역값이 합산된 라벨들을 저장해주는 벡터이다. 만약 현재 4방위로 탐색된 위치의 라벨링 넘버가 arr에 들어있다면, 이는 이미 한 번 합산된 영역임을 뜻한다. 때문에 visited 를 true로 변경해주고 for문을 종료한다.
(6) 만약 visited가 false라면 해당 위치는 아직 합산하지 않았음을 뜻한다. cnt에 값을 더해주고 arr벡터에 해당 라벨링 넘버를 추가해준다.
(7) 4방위로 탐색을 종료하고, 여탯껏 누적된 cnt의 값 % 10을 해당 위치에 저장해준다.
5. 최종적으로 저장된 배열을 출력한다.
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(ch[i][j]) cout << 0;
else cout << v[i][j];
}
cout << "\n";
}이때 ch[i][j]가 true일 경우, 0으로 그룹화가 된 지역임을 뜻한다. 이때는 그냥 0을 출력해주면 된다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n,m,my[]={1,0,-1,0},mx[]={0,1,0,-1},ny,nx,y,x,cnt,num=1,label[1001][1001],v[1001][1001];
char temp;
bool ch[1001][1001];
void bfs(int a, int b, int labeling){
queue<pair<int,int>> q1;
queue<pair<int,int>> q2;
cnt = 1;
label[a][b] = labeling;
q1.push({a,b});
q2.push({a,b});
ch[a][b] = true;
while(!q1.empty()){
y = q1.front().first;
x = q1.front().second;
q1.pop();
for(int i=0; i<4; i++){
ny = y+my[i];
nx = x+mx[i];
if(ny>=1&&ny<=n&&nx>=1&&nx<=m&&!ch[ny][nx]&&v[ny][nx]==0){
ch[ny][nx] = true;
cnt++;
label[ny][nx] = labeling;
q1.push({ny,nx});
q2.push({ny,nx});
}
}
}
while(!q2.empty()){
y = q2.front().first;
x = q2.front().second;
q2.pop();
v[y][x] = cnt;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin >> temp;
v[i][j] = temp-'0';
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(v[i][j]==0&&!ch[i][j]) bfs(i,j,num++);
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(!ch[i][j]){ //방문하지 않은 곳 = 벽
vector<int> arr;
cnt = 1;
for(int x=0; x<4; x++){
bool visited = false;
ny = i+my[x];
nx = j+mx[x];
if(ny>=1&&ny<=n&&nx>=1&&nx<=m&&ch[ny][nx]){
for(int z=0; z<arr.size(); z++){
if(arr[z]==label[ny][nx]) visited = true;
}
if(!visited){
arr.push_back(label[ny][nx]);
cnt += v[ny][nx];
}
}
}
v[i][j] = cnt%10;
}
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(ch[i][j]) cout << 0;
else cout << v[i][j];
}
cout << "\n";
}
return 0;
}
처음에는 생각없이 무작정 1인 지역들에 한해서 모두 BFS, DFS를 진행했다가 딱 한 번 시간초과가 나와버렸다.
생각해보니 굳이 모든 위치를 BFS하지 않아도 그룹핑 + 라벨링을 통해 결과를 구할 수 있음을 깨달았고, 구현한 결과 정답이 나왔다.
이 문제는 DFS, BFS, 그룹핑, 라벨링이라는 DFS-BFS유형과 관련된 핵심 요소들을 모두 활용할 수 있어서 좋은 문제였다.
참고로 위 코드는 120ms가 소요되었다.
'🖥️ CS > Baekjoon Algorithms' 카테고리의 다른 글
| 백준 16933번 벽 부수고 이동하기 3 - tuple (C++) (0) | 2021.05.21 |
|---|---|
| 백준 14442번 벽 부수고 이동하기 2 (C++) (0) | 2021.05.21 |
| 백준 12886번 돌 그룹 (C++) (0) | 2021.05.20 |
| 백준 14502번 연구소 (C++) (0) | 2021.05.18 |
| 백준 2531번 회전 초밥 (C++) (0) | 2021.05.17 |