백준 2931번: 가스관(Python/Java)

https://www.acmicpc.net/problem/2931

2931번: 가스관

 

 

 

접근

---

가장 간단하게 생각해보면, 각 칸마다 접근해서 인접 좌표의 블록 유형을 하나하나 확인해 끊겨있는지 확인하고 끊겨있다면 이를 이어 줄 수 있는 블록을 찾아 넣으면 된다. 단순 구현 문제기 때문에 이렇게 풀면 당연하게도 정답이 나온다! 나는 이 원리를 기본으로 코드 길이를 줄이고 더 효율적으로 작성할 수 있는 방법을 찾아보았다.

 

구현하면서 가장 신경 썼던 점은 해당 구간마다 블록 유형을 체크하지 않도록 하는 것이었다. 다시 말해 현재 탐색하는 구간의 블록이 "|"인지, "+"인지 체크하지 않아야 한다고 생각했다. 그렇다면 어떻게 해야 상하좌우와 연결되는 블록을 찾을 수 있을까? 내가 생각 해낸 방법은 상하좌우 칸의 블록이 현재 탐색하는 칸 쪽으로 연결되는 블록인지 확인하는 것이다. 예를 들어 생각해 보자.

 

위와 같은 그림인 상황에서 끊겨있는 곳에 어떤 블록이 필요한지 확인해야 한다고 가정해보자. 만일 상하좌우 인접한 칸의 블록의 모양을 그때마다 확인해야 한다면 많은 조건문이 필요할 것이다. 그렇다면 조금 생각을 바꿔서 상하좌우 인접한 칸이 현재 칸 쪽으로 연결되는 상황인지 확인하는 것은 어떨까?

 

위 그림과 같이 상하좌우 칸이 현재 위치 쪽으로 연결되는 상황인지 확인한 후에, 해당 경우에 맞는 블록을 껴넣는 것이다. 자그레브와 모스크바는 어느 쪽이든지 연결될 수 있도록 되어있기 때문에 네 면 모두 연결될 수 있다고 조건을 넣으면 된다. 이를 활용하면 보다 효율적인 코드를 작성할 수 있을 것으로 생각한다.

 

이 상황에서도 예외는 있다. 바로 자그레브와 모스크바 중 딱 한 곳만 연결되는 경우, 혹은 다른 칸들이 있음에도 불구하고 자그레브에서 모스크바 쪽으로 바로 연결할 수 있는 경우다.

 

첫 번째 경우가 문제가 되는 이유는 다른 칸이 비어있음에도 불구하고 자그레브 혹은 모스크바 둘 중 한 곳을 먼저 만났을 경우 해당 칸과 연결되는 블록을 넣고 결괏값을 출력하게 되기 때문이다. 이를 해결하기 위해선 '불필요한 블록은 존재하지 않는다'라는 조건을 생각해야 한다. 해당 조건에 따르면 그냥 혼자 덩그러니 놓여있는 블록은 없다. 무조건 상하좌우 어느 쪽이 되었든 각기 다른 블록을 연결해야 한다. 블록 7개 모두 무조건 다른 두 개 혹은 네 개의 블록이 연결되도록 주어져있다. 즉, 단 한 곳만 연결되는 칸이 있다면 그곳은 무조건 자그레브 혹은 모스크바 중 한 곳을 연결한 곳이다. 때문에 상하좌우 중 연결되는 곳이 딱 한 곳 있다면 과감하게 넘어가 주자.

 

두 번째 경우가 문제가 되는 경우 또한 위에서 언급한 문제 조건 때문이다. 만일 다른 블록들을 모두 무시하고 모스크바와 자그레브가 직통으로 연결된다면 다른 블록들이 불필요한 존재가 된다. 무엇보다 '모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다'라는 문제 조건에 의해 애초에 두 도시가 직통으로 연결될 수 없다. 때문에 상하좌우를 살펴봤을 때 자그레브와 모스크바 둘 다 있는지 확인해주고 둘 다 존재한다면 자그레브와 모스크바가 있는 칸은 연결 조건에서 빼주면 된다.

 

"만약 다른 블록 없이 자그레브와 모스크바만 있다면 어떡하나요?" 앞서 얘기했듯이 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어지기 때문에 애초에 그런 건 입력조차 되지 않으니 걱정하지 말자.

 

 

 

풀이

---

Python

upDown = [-1, 1, 0, 0]
leftRight = [0, 0, -1, 1]
sideCheck = [1, 0, 3, 2]
markList = ["|", "-", "+", "1", "2", "3", "4", "M", "Z"]
markSideList = [[1, 1, 0, 0], [0, 0, 1, 1], [1, 1, 1, 1], [0, 1, 0, 1], [1, 0, 0, 1], [1, 0, 1, 0], [0, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1]]


height, width = map(int, input().split())
board = [[[0 for i in range(4)] for i in range(width)] for i in range(height)]
originBoard = [["" for i in range(width)] for i in range(height)]

result = ""
resultLocation = [-1, -1]
for i in range(height):
    firstLine = input()
    for j in range(width):
        originBoard[i][j] = firstLine[j]

        for k in range(9):
            if firstLine[j] == markList[k]:
                board[i][j] = markSideList[k]
                break

for i in range(height):
    for j in range(width):
        subList = [0, 0, 0, 0]
        subCheck = 0
        mLocation = -1
        zLocation = -1
        if originBoard[i][j] == ".":
            for k in range(4):
                subHeight = (i + upDown[k])
                subWidth = (j + leftRight[k])

                if 0 <= subHeight < height and 0 <= subWidth < width:
                    subList[k] = board[subHeight][subWidth][sideCheck[k]]
                    
                    if originBoard[subHeight][subWidth] == "M":
                        mLocation = k
                    elif originBoard[subHeight][subWidth] == "Z":
                        zLocation = k

                    if subList[k] == 1:
                        subCheck += 1

        if mLocation != -1 and zLocation != -1:
            subList[mLocation] = 0
            subList[zLocation] = 0

        if subCheck > 1:
            for k in range(7):
                if subList == markSideList[k]:
                    result = markList[k]
                    resultLocation = [i, j]
                    break

print((resultLocation[0]+1), (resultLocation[1]+1), result)

 

Java

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        int[] upDown = {-1, 1, 0, 0};
        int[] leftRight = {0, 0, -1, 1};
        int[] sideCheck = {1, 0, 3, 2};
        String[] markList = {"|", "-", "+", "1", "2", "3", "4", "M", "Z"};
        int[][] markSideList = {{1, 1, 0, 0}, {0, 0, 1, 1}, {1, 1, 1, 1}, {0, 1, 0, 1}, {1, 0, 0, 1}, 
                                {1, 0, 1, 0}, {0, 1, 1, 0}, {1, 1, 1, 1}, {1, 1, 1, 1}};

        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int height = Integer.parseInt(firstLine[0]), width = Integer.parseInt(firstLine[1]);
        
        String[][][] board = new String[height][width][4];
        String[][] originBoard = new String[height][width];

        for(int i = 0 ; i < height ; i++){
            for(int j = 0 ; j < width ; j++){
                for(int k = 0 ; k < 4 ; k++){
                    board[i][j][k] = "0";
                }
            }
        }

        String result = "";
        int[] resultLocation = {-1, -1};
        for(int i = 0 ; i < height ; i++){
            String[] secondLine = (scan.nextLine()).split("");
            for(int j = 0 ; j < width ; j++){
                originBoard[i][j] = secondLine[j];

                for(int k = 0 ; k < 9 ; k++){
                    if(secondLine[j].equals(markList[k])){
                        for(int l = 0 ; l < 4 ; l++){
                            board[i][j][l] = Integer.toString(markSideList[k][l]);
                        }
                    }
                }
            }
        }

        for(int i = 0 ; i < height ; i++){
            for(int j = 0 ; j < width ; j++){
                int[] subList = {0, 0, 0, 0};
                int subCheck = 0;
                int mLocation = -1;
                int zLocation = -1;

                if(originBoard[i][j].equals(".")){
                    for(int k = 0 ; k < 4 ; k++){
                        int subHeight = (i + upDown[k]);
                        int subWidth = (j + leftRight[k]);

                        if(subHeight >= 0 && subHeight < height && subWidth >= 0 &&  subWidth < width){
                            subList[k] = Integer.parseInt(board[subHeight][subWidth][sideCheck[k]]);
                            if(originBoard[subHeight][subWidth].equals("M")){
                                mLocation = k;
                            }else if(originBoard[subHeight][subWidth].equals("Z")){
                                zLocation = k;
                            }

                            if(subList[k] == 1){
                                subCheck++;
                            }
                        }
                    }

                }

                if(mLocation != -1 && zLocation != -1){
                    subList[mLocation] = 0;
                    subList[zLocation] = 0;
                }

                if(subCheck > 1){
                    for(int k = 0 ; k < 7 ; k++){
                        boolean thisCheck = true;
                        for(int l = 0 ; l < 4 ; l++){
                            if(subList[l] != markSideList[k][l]){
                                thisCheck = false;
                                break;
                            }
                        }

                        if(thisCheck){
                            result = markList[k];
                            resultLocation = new int[] {i, j};
                            break;
                        }
                    }
                }
            }
        }

        System.out.println((resultLocation[0]+1) + " " + (resultLocation[1]+1) + " " + result);

    }

}

 

 

 

후기

---

조건에 맞게 각 블록 기호마다 if문을 각각 때려 박으면 풀리기야 했겠지만 그렇게 푸는 건 의미가 없다는 생각이 들었다. 최대한 기호를 직접적으로 비교하는 방법은 피하고자 했는데 어쨌든 제대로 먹힌 것 같아서 다행이다.

 

그렇다고 해서 마냥 만족스러운 풀이는 또 아니다. 일단 배열 전체를 탐색했기 때문에 연산이 많아졌다. 기호가 있는 부분들 위주로 탐색했으면 좋았을 것 같다 생각한다. 또 자바로 문제를 풀 때, 배열을 비교하는 방식에서 아쉬움을 느꼈다. 파이썬 같은 경우는 '==' 연산 하나로 되지만, 자바는 그렇게 간단치가 않다. 이 부분 또한 확인해야 하는 문제점이라 생각한다.