백준 19952번: 인성 문제 있어?? (Python/Java)

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

19952번: 인성 문제 있어??

 

 

 

접근

---

전형적인 너비 우선 탐색 문제에 약간의 구현을 더한 문제다. 때문에 너비 우선 탐색 부분은 기본 개념을 찾아보는 걸로 하고, '약간의 구현' 부분을 살펴보도록 하자.

 

일반적으로 너비 우선 탐색을 할 경우, 시작 점에서 도착 점까지의 거리를 물어보는 경우가 많다. 그런데 여기서 물어보는 것은 내 남은 체력으로 목표 위치까지 갈 수 있는지 없는 지다. 때문에 체력을 매번 체크해줘야 한다. 만일 체력이 0보다 많이 남았다면 다음 칸 탐색을 할 수 있다. 하지만 현재 체력이 0이라면 더 이상 움직일 수 없다. 즉, Queue에서 현재 지점을 꺼냈다면, 체력을 먼저 확인해야 한다.

 

다음은 목표지점 도달 여부다. 이 부분에서 보통 두 가지로 나뉜다. Queue에서 꺼낸 직후 현재 지점이 도착지점인지 확인하기 혹은 다음 지점을 탐색한 후 현재 탐색한 다음 지점이 도착지점인지 확인하기. 후자 방법으로 해야 연산이 훨씬 줄어들지만 개인적으로는 작성 코드가 줄어들고 조건문이 적어진다는 이유로 전자로 하곤 했다. 하지만 여기서는 체력이 0이 됨과 동시에 도착 지점에 도착하는 경우도 성공으로 본다. (문제 조건 상, 체력은 해당 지점 탐색이 끝난 이후에 줄어들기 때문) 이 부분에서 체력과 도착 여부 확인을 함께 하면 (물론 할 수는 있지만) 코드가 복잡해지게 된다. 때문에 후자 방법으로 도착 여부를 확인하도록 하자.

 

물론 개인적인 의견이기 때문에 본인이 편한 방법으로 작성하면 된다. 요점은 체력이 0이 되는 시점과 목표 지점 도착 시점이 같을 때는 도착한 게 맞다는 것으로 처리해야 한다는 것이다.

 

 

 

풀이

---

Python

from collections import deque

upDown = [-1, 1, 0, 0]
leftRight = [0, 0, -1, 1]

testCase = int(input())

for i in range(testCase):
    height, width, obstacle, power, startHeight, startWidth, goalHeight, goalWidth = map(int, (input()).split())
    
    board = [[0 for i in range(width)] for i in range(height)]
    visitList = [[False for i in range(width)] for i in range(height)]

    for i in range(obstacle):
        subHeight, subWidth, subLength = map(int, (input()).split())
        board[subHeight-1][subWidth-1] = subLength

    bfsDeque = deque()
    bfsDeque.append([(startHeight-1), (startWidth-1), power])

    resultCheck = False
    while bfsDeque:
        thisDeque = bfsDeque.popleft()

        if thisDeque[2] == 0:
            break

        for i in range(4):
            subHeight = (thisDeque[0] + upDown[i])
            subWidth = (thisDeque[1] + leftRight[i])

            if 0 <= subHeight < height and 0 <= subWidth < width:
                if not visitList[subHeight][subWidth]:
                    if board[thisDeque[0]][thisDeque[1]] >= board[subHeight][subWidth]:
                        visitList[subHeight][subWidth] = True
                        bfsDeque.append([subHeight, subWidth, (thisDeque[2] - 1)])

                        if subHeight == (goalHeight - 1) and subWidth == (goalWidth - 1):
                            resultCheck = True
                            break

                    else:
                        if thisDeque[2] >= (board[subHeight][subWidth] - board[thisDeque[0]][thisDeque[1]]):
                            bfsDeque.append([subHeight, subWidth, (thisDeque[2] - 1)])

                            if subHeight == (goalHeight - 1) and subWidth == (goalWidth - 1):
                                resultCheck = True
                                break

        if resultCheck:
            break

    if resultCheck:
        print("잘했어!!")
    else:
        print("인성 문제있어??")

 

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    
    static int[] upDown = {-1, 1, 0, 0}, leftRight = {0, 0, -1, 1};

    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
        int testCase = Integer.parseInt(scan.nextLine());

        for(int i = 0 ; i < testCase ; i++){
            
            String[] firstLine = (scan.nextLine()).split(" ");
            int height = Integer.parseInt(firstLine[0]), width = Integer.parseInt(firstLine[1]);
            int obstacle = Integer.parseInt(firstLine[2]), power = Integer.parseInt(firstLine[3]);
            int startHeight = Integer.parseInt(firstLine[4]), startWidth = Integer.parseInt(firstLine[5]);
            int goalHeight = Integer.parseInt(firstLine[6]), goalWidth = Integer.parseInt(firstLine[7]);

            int[][] board = new int[height][width];
            boolean[][] visitList = new boolean[height][width];

            for(int j = 0 ; j < obstacle ; j++){
                String[] secondLine = (scan.nextLine()).split(" ");
                int subHeight = Integer.parseInt(secondLine[0]);
                int subWidth = Integer.parseInt(secondLine[1]);
                int subLength = Integer.parseInt(secondLine[2]);

                board[subHeight-1][subWidth-1] = subLength;
            }

            Queue<int[]> bfsQueue = new LinkedList<>();
            bfsQueue.add(new int[] {(startHeight-1), (startWidth-1), power});

            boolean resultCheck = false;
            loop:
            while(!bfsQueue.isEmpty()){
                int[] thisQueue = bfsQueue.poll();

                if(thisQueue[2] == 0){
                    break;
                }

                for(int j = 0 ; j < 4 ; j++){
                    int subHeight = (thisQueue[0] + upDown[j]);
                    int subWidth = (thisQueue[1] + leftRight[j]);

                    if(subHeight >= 0 && subHeight < height && subWidth >= 0 && subWidth < width){
                        if(!visitList[subHeight][subWidth]){
                            if(board[thisQueue[0]][thisQueue[1]] >= board[subHeight][subWidth]){
                                visitList[subHeight][subWidth] = true;
                                bfsQueue.add(new int[] {subHeight, subWidth, (thisQueue[2]-1)});
                            
                                if(subHeight == (goalHeight-1) && subWidth == (goalWidth-1)){
                                    resultCheck = true;
                                    break loop;
                                }
                            
                            }else{
                                if(thisQueue[2] >= (board[subHeight][subWidth] - board[thisQueue[0]][thisQueue[1]])){
                                    bfsQueue.add(new int[] {subHeight, subWidth, (thisQueue[2]-1)});
                                
                                    if(subHeight == (goalHeight-1) && subWidth == (goalWidth-1)){
                                        resultCheck = true;
                                        break loop;
                                    }
                                }
                            }
                        }
                    }
                }
            }

            if(resultCheck){
                System.out.println("잘했어!!");
            }else{
                System.out.println("인성 문제있어??");
            }

        }

    }

}

 

 

 

후기

---

요즘 회사 일이 너무 바쁘고 야근이 잦아 제대로 공부를 못하고 있었다. 때문에 제대로 문제를 풀지 못했는데, 오랜만에 시간이 남아 골드 4 문제를 풀었다. 물론 난이도에 비해 쉬운 편이기도 했지만... 역시 너비 우선 탐색 문제가 확실히 풀기 쉽다.

 

이 문제의 난이도를 떠나서 break문을 여러 조건에 따라 나누는 건 언제나 귀찮고 헷갈리는 일이다. 이 문제 또한 간단하긴 하지만 그런 문제였는데, 문제의 조건을 정확하게 파악하고 해당 조건 만족 여부를 제대로 파악하는 습관을 들여야 할 것 같다.