[BOJ] 2931. 가스관

BFS를 이용하여 빈칸을 찾는 문제이다.

M에서 시작하여 다음파이프로 이동하면서 만나는 첫번째 빈칸에서 적합한 파이프를 찾는 문제이다. 그 빈칸의 파이프는 해당 빈칸과 연결된 모든 파이프들을 서로 연결시킬수 있는 모양이므로 체크해줘야할 조건이 상당히 많았다. 조건을 체크하는 과정에서 어이없게 실수하는 부분이 있어서 상당히 오랜시간 푼 문제였다. 

BFS를 사용하는 방법 말고도 모든 빈칸을 확인하면서 파이프와 연결되지 않은 곳이 있다면 그 빈칸에 대해 해당하는 파이프 모양을 찾아주는 방법으로도 문제를 접근할 수 있다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_2931_가스관 {
    
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static List<Integer>[] pipe;
    
    static int[][] map;
    static int R,C;
    static boolean[][] visit;
    
    static Queue<Pos> queue;
    
    static class Pos{
        int i,j;
        Pos(int i,int j){
            this.i=i;this.j=j;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        
        map=new int[R][C]; visit=new boolean[R][C];
        Pos start=null;
        for(int i=0;i<R;i++) {
            String str=br.readLine();
            for(int j=0;j<C;j++) {
                char ch =str.charAt(j);
                switch (ch) {
                case '|':map[i][j]=1;break;
                case '-':map[i][j]=2;break;
                case '+':map[i][j]=3;break;
                case '1':map[i][j]=4;break;
                case '2':map[i][j]=5;break;
                case '3':map[i][j]=6;break;
                case '4':map[i][j]=7;break;
                case 'M':map[i][j]=-2; start=new Pos(i, j); visit[i][j]=true; break;
                case 'Z':map[i][j]=-2; visit[i][j]=true;break;
                }
            }
        }
        
        pipe=new ArrayList[8];
        for(int i=1;i<=7;i++)
            pipe[i]=new ArrayList<>();
        
        pipe[1].add(0);pipe[1].add(2);                                    // | 북남
        pipe[2].add(1);pipe[2].add(3);                                    // - 동서
        pipe[3].add(0);pipe[3].add(1);pipe[3].add(2);pipe[3].add(3);    // + 동서남북
        pipe[4].add(1);pipe[4].add(2);                                    // 1 동남
        pipe[5].add(0);pipe[5].add(1);                                    // 2 북동
        pipe[6].add(0);pipe[6].add(3);                                    // 3 북서
        pipe[7].add(3);pipe[7].add(2);                                    // 4 남서
        
        
        queue=new LinkedList<>();
        //첫파이프 찾기
        for(int dir=0;dir<4;dir++) {
            int nextI=start.i+di[dir];
            int nextJ=start.j+dj[dir];
            
            if(nextI<0 || nextI>=R || nextJ<0 ||nextJ>=C)
                continue;
            
            if(map[nextI][nextJ]>=1 && map[nextI][nextJ]<=7) {    //파이프이면
                if(isConnected(dir, map[nextI][nextJ])==true) {    //연결되어 있다면
                    visit[nextI][nextJ]=true;
                    queue.offer(new Pos(nextI, nextJ));
                    break;
                }
            }
        }
        bfs();
    }
    
    
    static void bfs() {
        while(!queue.isEmpty()) {
            Pos cur =queue.poll();
            int curPipe=map[cur.i][cur.j];
            
//            System.out.println(cur.i+","+cur.j);
            
            for(int dir : pipe[curPipe]) {
                int nextI=cur.i+di[dir];
                int nextJ=cur.j+dj[dir];
                
                if(nextI<0 || nextI>=R || nextJ<0 || nextJ>=C)
                    continue;
                
                int nextPipe=map[nextI][nextJ];
                
                //빈칸이 아닌 경우 0 = 빈칸, -2 = 도시
                if(visit[nextI][nextJ]==false && map[nextI][nextJ]!=0 && map[nextI][nextJ]!=-2) {
                    if(isConnected(dir, nextPipe)==true) {
                        visit[nextI][nextJ]=true;
                        queue.offer(new Pos(nextI, nextJ));
                    }
                }
                
                //빈칸인 경우
                if(visit[nextI][nextJ]==false && map[nextI][nextJ]==0) {
                    for(int p=1;p<=7;p++) {        //1번부터 7번까지 파이프 가능한지 확인
                        if(findPipe(nextI,nextJ,p)==true) {
                            print(nextI, nextJ, p);
                            return;
                        }
                    }
                }
            }
        }
    }
    
    //현재 위치에서 파이프가 다른 방향으로 이어지는지 확인
    static boolean findPipe(int i,int j,int p) {
        int count=0;
        
        for(int dir=0;dir<4;dir++) {
            int nextI=i+di[dir];
            int nextJ=j+dj[dir];
            
            if(nextI<0 || nextI>=R || nextJ<0 || nextJ>=C)
                continue;
            if(map[nextI][nextJ]>=1 && map[nextI][nextJ]<=7 && 
                    isConnected(dir, map[nextI][nextJ])==true)
                count+=1;
        }
        
        int count2=0;
        for(int dir : pipe[p]) {
            int nextI=i+di[dir];
            int nextJ=j+dj[dir];
            
            if(nextI<0 || nextI>=R || nextJ<0 || nextJ>=C)
                return false;
            if(map[nextI][nextJ]==0 || map[nextI][nextJ]==-2)
                return false;
            if(isConnected(dir, map[nextI][nextJ])==false)
                return false;
            count2+=1;
            
        }
        
        if(count==count2)
            return true;
        return false;
    }
    
    
    //다음에 갈 파이프가 현재ㅐ 방향의 반대 방향을 가지는지 확인
    static boolean isConnected(int dir, int nextPipe) {        
        int oppDir=oppDir(dir);
        if(pipe[nextPipe].contains(oppDir)==true)
            return true;
        return false;
    }
    
    //반대방향 리턴
    static int oppDir(int dir) {
        if(dir==0)    return 2;
        if(dir==1)    return 3;
        if(dir==2)    return 0;
        if(dir==3)    return 1;
        return -1;
    }
    
    static void print(int i,int j,int pipe) {
        System.out.print((i+1)+ " "+ (j+1) + " ");
        switch (pipe) {
        case 1: System.out.println("|"); break;
        case 2: System.out.println("-"); break;
        case 3: System.out.println("+"); break;
        case 4: System.out.println("1"); break;
        case 5: System.out.println("2"); break;
        case 6: System.out.println("3"); break;
        case 7: System.out.println("4"); break;
        }
    }
}