[백준] 가스관(2931)

문제 링크 : [백준] 가스관(2931)

문제 설명

N * M 배열이 주어지고, 각 칸은 시작점 M과 도착점 Z가 있고, 각 파이프 모양들을 따라 시작점에서 도착점까지 갈 수 있는 지도가 주어집니다. 그 중에 한칸만 지웠을 때, 지운 칸의 위치와 지워진 칸의 원래 파이프를 출력해야 합니다.

입력

R(Row 수, 1<=R<=25)
C(Column 수, 1<=C<=25)
R * C 크기의 지도

3 7
.......
.M-.-Z.
.......

출력

2 4 -

카테고리

#구현

시간 복잡도 상한

크기가 매우 작아서 왠만하면 됩니다.

해결 방법

1. 시작점과 도착점(M, Z)에서 나갈 수 있는 파이프가 있는지 확인합니다.
   1-1. 나가는 파이프가 없다면 반드시 인접한 칸에서 다른 파이프로 연결이 되어야합니다.
2. 모든 점을 돌면서 비어있는 한 점(.)을 만나면, 그 점의 상하좌우에서 현재 점으로 연결되는 파이프가 있는지 확인합니다.
   2-1. 현재 점이 비어있는데, 그 점으로 올 수 있는 파이프가 있다면, 파이프의 연결이 끊어져 있는 것입니다.
3. 비어있는 점으로 올 수 있는 파이프가 4개라면 반드시 + 가 삭제 된 것이며, 2개라면 두 방향을 잇는 파이프를 출력하면 됩니다.
4. 구현 편의를 위하여, 1에서 시작점이나 도착점에서 나가는 파이프가 없다면, *로 치환을 하고, 2에서 *를 만나면 어떤 방향에서도 올 수 있는 파이프로 간주하였습니다.

코드

#include<cstdio>
#include<vector>
#include<string.h>
using namespace std;
int n,m,o[4][2]={ {1,0},{0,1},{-1,0},{0,-1} },i,j,k,l,t,u,nx,ny;
char d[27][27],v[4][6]={"|+23*","-+34*","|+14*","-+12*"};
vector<int>w;
int main(){
    memset(d,'.',sizeof(d));
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%s",d[i]+1);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(d[i][j]=='M'||d[i][j]=='Z'){
                int a=1;
                for(k=0;k<4;k++){
                    nx=i+o[k][0];
                    ny=j+o[k][1];
                    for(l=0;l<5;l++)if(d[nx][ny]==v[k][l])a=0;
                }
                if(a)d[i][j]='*';
                else d[i][j]='/';
            }
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(d[i][j]=='.'){
                for(t=k=0;k<4;k++){
                    nx=i+o[k][0];
                    ny=j+o[k][1];
                    for(l=0;l<5;l++)if(d[nx][ny]==v[k][l])w.push_back(k);
                }
                if(!w.empty()){
                    printf("%d %d ",i,j);
                    if(w.size()==4){
                        printf("%c",'+');
                        return 0;
                    }
                    if(w.size()==2){
                        if(w[0]==0){
                            if(w[1]==1)printf("1");
                            if(w[1]==2)printf("|");
                            if(w[1]==3)printf("4");
                        }
                        if(w[0]==1){
                            if(w[1]==2)printf("2");
                            if(w[1]==3)printf("-");
                        }
                        if(w[0]==2){
                            if(w[1]==3)printf("3");
                        }
                        return 0;
                    }
                }
            }
        }
    }
}