Baekjoon 2931 가스관 JAVA

2931번: 가스관

문제

러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.

이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다.

가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직, 수평)으로 흘러야 한다.

파이프 라인의 설계를 마친 후 두 사람은 잠시 저녁을 먹으러 갔다. 그 사이 해커가 침임해 블록 하나를 지웠다. 지운 블록은 빈 칸이 되어있다.

해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오.

 

조건

[입력]

첫째 줄에 유럽의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 25)

다음 R개 줄에는 C개 글자가 주어지며, 다음과 같은 글자로 이루어져 있다.

• 빈칸을 나타내는 '.'
• 블록을 나타내는 '|'(아스키 124), '-', '+', '1', '2', '3', '4'
• 모스크바의 위치를 나타내는 'M'과 자그레브를 나타내는 'Z'. 두 글자는 한 번만 주어진다.

항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어진다, 또, 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다. 또, 불필요한 블록이 존재하지 않는다. 즉, 없어진 블록을 추가하면, 모든 블록에 가스가 흐르게 된다.

 

[출력]

지워진 블록의 행과 열 위치를 출력하고, 어떤 블록이었는지를 출력한다.

 

풀이

해당 문제는 map와 가스관 종류가 주어졌을 때 M과 Z를 연결하는 가스관 중 끊어진 부분과 해당 부분에 들어가야 할 가스관의 종류를 구하는 문제다.

전형적인 구현 문제였으며 bfs를 이용하여 해결했다. 내 생각은 다음과 같다. 먼저 시작점에서 bfs를 돌면서 끊어진 부분을 찾고 알맞은 가스관 종류를 찾는 것이다. 로직은 아래와 같이 구현하였다.

 

1. map를 입력받으면서 M과 Z에 대해서 좌표를 리스트에 담아둔다.

2. bfs를 돌리면서 끊어진 부분의 좌표를 찾는다.

    1. 먼저 M과 Z에 대해서 4방향 중 가스관이 연결된 좌표값 하나를 찾아 큐에 담는다.

        (M, Z는 모두 파이프와 처음엔 연결되어있다 하나만 체크해도 해결 가능)

    2. bfs를 돌리면서 끊어진 부분을 찾는다.

        1. 각 가스관 별 이동할 수 있는 방향을 배열에 담고 해당 방향으로 탐색한다.

        2. 탐색 가능한 방향인데 가스관이 없으면 좌표값을 경신하고 bfs를 종료한다.

3. 끊어진 부분에 대해 딱 맞는 파이프 모양을 찾는다.

    1. 4방향을 체크하면서 연결될 수 있는 부분을 체크한다.

    2. 조건문을 통해 연결되는 부분과 딱 맞는 파이프를 경신한다.

4. 최종 출력한다.

 

해당 문제는 디버깅을 많이 했고, 각종 오류들이 발생했던 문제다. 오류가 발생할 때마다 코드를 체크해가면서 해결해나갔고 최종적으로 50%에서 해결을 하지 못해 질문게시판을 보던 중 하나의 테케에 대해 체크를 해주지 않은 걸 알게 되었고 해결할 수 있었다.

 

문제를 좀 더 꼼꼼히 봐야 할 거 같다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int R, C, Y,X,dy[]={-1,0,1,0}, dx[]={0,1,0,-1}; // 상하좌우
    static char map[][], ans;
    static boolean visit[][];
    static Queue<Node> queue = new LinkedList<>();
    static List<Node> list = new ArrayList<>();
    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 char[R][C];
        visit = new boolean[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'M' || map[i][j] =='Z'){ // 리스트에 각각의 시작점을 담아둔다.
                    list.add(new Node(i,j));
                }
            }
        }
        bfs(); // bfs를 돌려서 끊어진 부분을 찾는다.
        check(); // 여기서는 끊어진 부분에 들어가 파이으 종류 찾기 
        System.out.println((Y+1) + " "+(X+1)+ " " + ans); // 출력할때 문제는 1,1 시작 나는 0,0 시작이므로 +1해준다
    }

    private static void check() {
        boolean d[] = new boolean[4];
        for (int i = 0; i < 4; i++) { // 끊어진 파이프 4방향을 체크하면서 연결될수있는 부분들에 대해 체크한다.
            int ny = Y + dy[i];
            int nx = X + dx[i];
            if(ny < 0 || nx < 0 || ny >= R || nx >= C || map[ny][nx] =='.')
                continue;
            if(i == 0 && ( map[ny][nx] =='|' || map[ny][nx] =='+' || map[ny][nx] =='1' || map[ny][nx] =='4'))
                d[i] = true;
            else if(i == 2  && (  map[ny][nx] =='|' || map[ny][nx] =='+' || map[ny][nx] =='2' || map[ny][nx] =='3'))
                d[i] = true;
            else if(i == 1 && (  map[ny][nx] =='-' || map[ny][nx] =='+' || map[ny][nx] =='3' || map[ny][nx] =='4'))
                d[i] = true;
            else if(i == 3 && (map[ny][nx] =='-' || map[ny][nx] =='+' || map[ny][nx] =='1' || map[ny][nx] =='2'))
                d[i] = true;
        }
        if(d[0] && d[1] && d[2] && d[3]) // 연결할수있는 파이프 방향을 체크해서 최종 값을 결정한다.
            ans = '+';
        else if(d[1] && d[3])
            ans = '-';
        else if(d[0] && d[2])
            ans = '|';
        else if(d[1] && d[2])
            ans = '1';
        else if(d[0] && d[1])
            ans = '2';
        else if(d[0] && d[3])
            ans = '3';
        else if(d[2] && d[3])
            ans = '4';
    }

    private static void bfs() {
        int index = 0;
        while(queue.isEmpty()){ // 시작점이 두개니깐 둘중 되는걸로 체크
            Node node = list.get(index++);
            visit[node.y][node.x]= true;
            for (int i = 0; i < 4; i++) {
                int ny = node.y + dy[i];
                int nx = node.x + dx[i];
                if(ny < 0 || nx < 0 || ny >= R || nx >= C || map[ny][nx] =='.' || map[ny][nx] =='M' || map[ny][nx] =='Z')
                    continue;
                visit[ny][nx] = true;
                queue.add(new Node(ny,nx)); // 시작점에서 인접한 파이프관 하나를 찾아서 큐에 넣음.
                break;
            }
        }

        while(!queue.isEmpty()){ // 큐가 빌때까지 bfs 돌려준다.
            Node node = queue.poll();
            if(map[node.y][node.x] =='Z' || map[node.y][node.x] =='M') // 큐에 출발점이 담길수도있음 이를 체크해준다
                continue;
            int[] d = null;
            if(map[node.y][node.x] == '|'){ // 각각의 경우의수에 따른 방향값을 배열로 저장한다.
                d = new int[]{0,2};
            }else if(map[node.y][node.x] == '-'){
                d = new int[]{1,3};
            }else if(map[node.y][node.x] == '+') {
                d = new int[]{0,1,2,3};
            }else if(map[node.y][node.x] == '1'){
                d = new int[]{1,2};
            }else if(map[node.y][node.x] == '2'){
                d = new int[]{0,1};
            }else if(map[node.y][node.x] == '3'){
                d = new int[]{0,3};
            }else if(map[node.y][node.x] == '4'){
                d = new int[]{2,3};
            }

            for (int i = 0; i < d.length; i++) { // 위에서 정한 방향만큼만 이동을 실시
                int ny = node.y + dy[d[i]];
                int nx = node.x + dx[d[i]];
                if(visit[ny][nx])
                    continue;
                if(map[ny][nx] =='.') { // 만약 막혀있다면 해당 부분이 끊어진 부분 좌표값 갱신하고 멈춘다.
                    Y = ny;
                    X = nx;
                    return;
                }
                visit[ny][nx] = true;
                queue.add(new Node(ny,nx));
            }
        }
    }
    static class Node{
        int y,x;
        Node(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드