가스관
문제 해석
RxC 배열의 각 칸은 비어있거나, 다음 그림과 같은 블록으로 이루어져있습니다.
가스는 M에서 Z로 흐릅니다. 흐르는 가스관 중 하나가 비어있을 때 어떤 가스관이 들어가야하는지 맞추는 문제입니다.
설계(15)
범위가 적어서 완전탐색으로 풀이가 가능한 문제입니다.
지문 중 주의할 점이 몇가지 있습니다.
- 항상 답이 존재하고, 가스의 흐름이 유일한 경우만 주어집니다.
- 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어집니다.
- 불필요한 블록이 존재하지 않습니다.
이 세가지 지문을 기준으로 설계하였습니다.
우선 2번 지문으로 비추어볼 때 M에서 상하좌우로 검색했을 때 가능한 방향은 한가지입니다. 이를 첫 방향으로 정해놓습니다.
다음으로 끊긴지점을 알아야 합니다. 끊긴 지점에 7가지 블록들을 채워넣어서 Z까지 도달할 수 있는지 여부를 찾습니다.
이 과정을 구현하는데 백트래킹 기법을 사용합니다.
매개변수는 {현재좌표 x,y, 현재 방향, 끊긴지점을 찾았는지 여부}
끊긴지점을 찾은 경우와 찾지 않은 경우를 mode변수를 이용하여 체크합니다.
각 블록들이 현재 방향으로 들어왔을 때 나가는 방향을 change_dir함수로 따로 구현해 놓습니다.
최종적으로 Z에 도착한 후, 모든 가스관을 지났는지 검토합니다.
여기서 주의할 점은 ‘+’의 경우 가로와 세로 모두 지나야 합니다.
이를 체크하기 위해서 boolean 3차원 배열을 이용합니다.
구현(30)
코드
#include <iostream>
using namespace std;
#define MAXN 25
char map[MAXN][MAXN];
bool visited[MAXN][MAXN][2];
int tx,ty;
int sx,sy,ex,ey;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int N,M;
char pattern[] = {'|','-','+','1','2','3','4'};
char ans,tmp_p;
bool finish;
int change_dir(int dir, char p){
if (p == 'Z') return dir;
else if (p == '|'){
if (dir == 1) return 1;
else if(dir==3) return 3;
}
else if (p == '-'){
if (dir ==0) return 0;
else if (dir == 2) return 2;
}
else if (p == '+'){
return dir;
}
else if (p =='1'){
if (dir ==2) return 1;
else if (dir ==3) return 0;
}
else if (p == '2'){
if (dir ==1) return 0;
else if (dir == 2) return 3;
}
else if (p == '3'){
if (dir ==1) return 2;
else if (dir == 0) return 3;
}
else if (p == '4'){
if (dir ==0) return 1;
else if (dir == 3) return 2;
}
return -1;
}
void backtrack(int x, int y, int dir, bool mode){
if (finish) return;
if (map[x][y] == 'Z'){
bool flag = false;
for (int i = 0 ; i <N && !flag; i++){
for (int j= 0;j<M;j++){
if (map[i][j]!='.'){
if (map[i][j]=='+' && (!visited[i][j][0] || !visited[i][j][1])){
flag = true;
break;
}
else if (map[i][j]!='+'&& !visited[i][j][0]){
flag = true;
break;
}
}
}
}
if (!flag){
ans = tmp_p;
finish = true;
}
return;
}
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx<0 || ny < 0 || nx>=N || ny>=M) return;
// 끊긴 지점인 경우 7가지 경우 모두 조사
if (!mode && map[nx][ny] =='.'){
tx = nx;
ty = ny;
for (int k = 0; k < 7; k++){
map[nx][ny] = pattern[k];
tmp_p = map[nx][ny];
int n_dir = change_dir(dir,map[nx][ny]);
if (n_dir ==-1) continue;
if (k == 2){
if (n_dir%2) visited[nx][ny][0] = true;
else visited[nx][ny][1] = true;
}
else{
visited[nx][ny][0] = true;
}
backtrack(nx,ny,n_dir,true);
if (k ==2){
if (n_dir%2) visited[nx][ny][0]= false;
else visited[nx][ny][1]=false;
}
else visited[nx][ny][0] = false;
}
}
else{
if (map[nx][ny]=='+'){
if (dir%2 && !visited[nx][ny][0]){
visited[nx][ny][0]= true;
backtrack(nx,ny,change_dir(dir,map[nx][ny]),mode);
visited[nx][ny][0]= false;
}
else if (!(dir%2) && !visited[nx][ny][1]){
visited[nx][ny][1] = true;
backtrack(nx,ny,change_dir(dir,map[nx][ny]),mode);
visited[nx][ny][1] = false;
}
}
else if (map[nx][ny]!='.'){
int n_dir = change_dir(dir,map[nx][ny]);
if (!visited[nx][ny][0] && n_dir!=-1){
visited[nx][ny][0] = true;
backtrack(nx,ny,n_dir,mode);
visited[nx][ny][0] = false;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 0 ;i <N; i++){
for (int j= 0;j<M;j++){
char tmp;
cin >> tmp;
map[i][j] = tmp;
if (map[i][j] == 'M') sx=i,sy=j;
else if (map[i][j] =='Z') ex=i,ey=j;
}
}
int idx;
for (idx = 0 ; idx <4;idx++){
int nx = sx + dx[idx];
int ny = sy + dy[idx];
if (nx < 0 || ny < 0 || nx>=N || ny>=M) continue;
if (map[nx][ny] !='.') break;
}
visited[sx][sy][0] = true;
backtrack(sx,sy,idx,false);
cout << tx+1 <<" "<< ty+1 <<" "<< ans<<"\n";
return 0;
}
디버깅
백트래킹 함수를 구현할 때, 비어있는 곳에 도착한 경우를 모두 끊긴 경우로 생각하여 mode변수를 사용하지 않았습니다.
어떠한 경우에는 끊긴지점에 블록을 놓고 다음 지점에서 빈곳에 도착하는 경우가 생길 수 있습니다.
이러한 오류를 방지하기 위해서 mode 매개변수를 추가하였습니다.
제출결과
0 ms
마무리
완전탐색문제였습니다.
다양한 해결법이 존재합니다. 가스관을 일일히 넣고 bfs or dfs로 탐색하는 경우 또한 가능할 것 같습니다.