백준 2931 가스관(구현, 시뮬레이션)

2931번: 가스관

SW Expert Academy

SWEA 탈주범 검거랑 비슷한 그림을 띄고 있지만 전혀 다른 문제다

 

출발지, 목적지를 잇는 완전한 길이 있었는데 그 중 하나를 없앴다는 것이다.

그것에 대한 정보를 구하는 문제

 

대체 어디를 없앴는지 과연 어떻게 알 수 있을까?

 

1. 출발지, 목적지에서 bfs를 출발하여 빈칸을 만날 때 이 빈칸들을 list에 저장하여 후보들을 정해놓고 2개의 list를 하나씩 비교해봤을 때 똑같은 부분이 바로 그 지점!

 

2. 빈칸에 대해 파이프를 바꿔야하니까 빈칸을 모두 살펴본다

빈칸에 대해 상하좌우를 돌리면서 다른 파이프가 연결되어있는지 cnt와 visited[]를 기억해두었다가 이용한다

 

cnt == 4 라는건 빈칸에 대해서 상하좌우에 모두 파이프가 연결되어있다는 것이니까 무조껀 '+' 가 된다

cnt == 2 가 나왔다면 2개가 연결된 파이프가 설치되어 있다는 뜻인데 어떤 모양의 파이프가 연결되어야 할지는 visited[]를 이용해서 방향을 맞춰서 알아내면 된다! 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    static char[][] map;
    static int R,C;
    static int dx[] = { -1, 1, 0, 0 };
    static int dy[] = { 0, 0, -1, 1 };
    static Map<Character, Integer> idx = new HashMap<>();
    static boolean[][] connection = { { true, true, false, false },
                                    { false, false, true, true },
                                    { true, true, true, true },
                                    { false, true, false, true },
                                    { true, false, false, true },
                                    { true, false, true, false },
                                    { false, true, true, false } };

    public static void main(String[] args) throws IOException {
        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];

        idx.put('|', 0);
        idx.put('-', 1);
        idx.put('+', 2);
        idx.put('1', 3);
        idx.put('2', 4);
        idx.put('3', 5);
        idx.put('4', 6);

        for (int i = 0; i < R; i++) {
            String t = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = t.charAt(j);
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == '.') {
                    boolean[] visited = new boolean[4];
                    int cnt = 0;
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (nx >= 0 && ny >= 0 && nx < R && ny < C ){
                                if(map[nx][ny] != '.' && map[nx][ny] != 'Z' && map[nx][ny] != 'M' ){
                                    if(connection[idx.get(map[nx][ny])][reverse_dir(k)]) {
                                        cnt++;
                                        visited[k] = true;
                                    }
                                }
                        }
                    }
                    if (cnt == 4) {
                        System.out.println((i + 1) + " " + (j + 1) + " +");
                        return;

                    } else if (cnt == 2) {
                        print(i + 1, j + 1, visited);
                        return;
                    }
                }
            }
        }
        
    }

    private static void print(int x, int y, boolean[] visited) {
        for (int i = 0; i < 7; i++) {
            if (i == 2)
                continue;
            boolean flag = true;
            for (int j = 0; j < 4; j++) {
                if (connection[i][j] != visited[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                System.out.println(x + " " + y + " " + pipe(i));
            }
        }

    }
    public static int reverse_dir(int d) {
        switch (d) {
            case 0:
                return 1;
            case 1:
                return 0;
            case 2:
                return 3;
            case 3:
                return 2;
        }
        return d;
    }
    
    public static char pipe(int i) {
        switch (i) {
            case 0:
                return '|';
            case 1:
                return '-';
            case 2:
                return '+';
            case 3:
                return '1';
            case 4:
                return '2';
            case 5:
                return '3';
            case 6:
                return '4';
        }
        return 0;
    }


}