백준 17267번: 상남자 (Python/Java)

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

17267번: 상남자

 

 

 

접근

---

간단한 너비 우선 탐색 알고리즘처럼 보이지만, 좌우 이동 횟수 제한 조건에 의해 굉장히 까다로워진 문제. 구현 자체는 어렵지 않으니, 우선 평소와 같이 현재 좌표에서 상하좌우 이동해 Queue에 넣고, 다시 Queue에서 값 하나 꺼내 또 상하좌우 이동하고... 이런 방식으로 구현한다고 생각해보자. 물론 좌우 이동 횟수도 꼭 체크를 해줘야겠지? 이렇게 풀면 너무 간단하게 예제 답을 구할 수 있다. 하지만 인생은 그렇게 생각한 대로 쉽게 흘러가지 않는 법. 다음과 같은 반례를 생각해보자. (아래 예제는 해당 문제 질문 게시글 https://www.acmicpc.net/board/view/37868에서 가져왔다)

 

자, 우선 첫 번째 그림은 땅의 구조다. 당연히 start라고 쓰여있는 지점에서부터 시작한다. 1번 경로는 start에서 좌측으로부터 이동하기 시작한 것, 2번 경로는 아래쪽으로 이동하기 시작한 것이다. 1번 경로에서는 시작할 때 왼쪽으로 이미 한번 움직였다. 즉, 이제 왼쪽으로 이동할 수 있는 경우는 없다. 때문에 [3, 2] 인덱스는 빈칸임에도 불구하고 왼쪽으로 이동할 수 없기 때문에 갈 수 없다. 하지만 2번 경로를 살펴보자. 2번 경로는 단 한 번도 왼쪽으로 이동한 적이 없기 때문에 [3, 2] 인덱스에 접근할 수 있다.

 

문제는 여기서부터 시작된다. 1번 경로는 [3, 1] 인덱스까지 9번의 이동만으로 도착 가능하다. 하지만 2번 경로는 [3, 1] 인덱스에 11번의 이동으로 도착한다. 즉, 이미 [3, 1] 인덱스는 1번 경로에 의해 이미 방문처리가 된 후고, 때문에 2번 경로를 통해 도착했을 때는 [3, 2]에 갈 수 있는지 없는지조차 확인할 수 없게 된다.

 

이를 해결하기 위해 사용한 방법은 위아래로 갈 수 있는 모든 부분을 탐색한 뒤, 양 옆으로 갈 수 있는지 확인하는 것이었다. 우선 위아래로 움직일 수 있는 부분을 모두 탐색해 Queue에 넣으면 중간에 좌우로 이동했을 때보다 갈림길에 먼저 도착할 수 있기 때문에 위와 같은 문제를 피할 수 있다.

 

 

 

풀이

---

Python

from collections import deque

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

height, width = map(int, input().split())
leftNum, rightNum = 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)]
bfsDeque = deque()
for i in range(height):
    firstLine = input()
    for j in range(width):
        board[i][j] = int(firstLine[j])

        if board[i][j] == 2:
            bfsDeque.append([i, j, 0, 0])
            visitList[i][j] = True

result = 1
while bfsDeque:
    thisDeque = bfsDeque.popleft()

    for i in range(2):
        thisHeight = thisDeque[0]
        while True:
            thisHeight += upDown[i]
            if 0 <= thisHeight < height and 0 <= thisDeque[1] < width:
                if not visitList[thisHeight][thisDeque[1]]:
                    if board[thisHeight][thisDeque[1]] != 1:
                        result += 1
                        visitList[thisHeight][thisDeque[1]] = True
                        bfsDeque.append([thisHeight, thisDeque[1], thisDeque[2], thisDeque[3]])
                    else:
                        break
            else:
                break
    
    if thisDeque[2] < leftNum:
        thisWidth = (thisDeque[1] + leftRight[2])

        if 0 <= thisDeque[0] < height and 0 <= thisWidth < width:
            if not visitList[thisDeque[0]][thisWidth]:
                if board[thisDeque[0]][thisWidth] != 1:
                    result += 1
                    visitList[thisDeque[0]][thisWidth] = True
                    bfsDeque.append([thisDeque[0], thisWidth, (thisDeque[2]+1), thisDeque[3]])

    if thisDeque[3] < rightNum:
        thisWidth = (thisDeque[1] + leftRight[3])

        if 0 <= thisDeque[0] < height and 0 <= thisWidth < width:
            if not visitList[thisDeque[0]][thisWidth]:
                if board[thisDeque[0]][thisWidth] != 1:
                    result += 1
                    visitList[thisDeque[0]][thisWidth] = True
                    bfsDeque.append([thisDeque[0], thisWidth, thisDeque[2], (thisDeque[3]+1)])

print(result)

 

Java

import java.util.LinkedList;
import java.util.Queue;
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};

        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int height = Integer.parseInt(firstLine[0]), width = Integer.parseInt(firstLine[1]);
        
        String[] secondLine = (scan.nextLine()).split(" ");
        int leftNum = Integer.parseInt(secondLine[0]), rightNum = Integer.parseInt(secondLine[1]);

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

        Queue<int[]> bfsQueue = new LinkedList<>();
        for(int i = 0 ; i < height ; i++){
            String[] thirdLine = (scan.nextLine()).split("");
            for(int j = 0 ; j < width ; j++){
                board[i][j] = Integer.parseInt(thirdLine[j]);

                if(board[i][j] == 2){
                    bfsQueue.add(new int[] {i, j, 0, 0});
                    visitList[i][j] = true;
                }
            }
        }

        int result = 1;
        while(!bfsQueue.isEmpty()){
            int[] thisQueue = bfsQueue.poll();

            for(int i = 0 ; i < 2 ; i++){
                int thisHeight = thisQueue[0];
                while(true){
                    thisHeight += upDown[i];

                    if(thisHeight >= 0 && thisHeight < height && thisQueue[1] >= 0 && thisQueue[1] < width){
                        if(!visitList[thisHeight][thisQueue[1]]){
                            if(board[thisHeight][thisQueue[1]] != 1){
                                result++;
                                visitList[thisHeight][thisQueue[1]] = true;
                                bfsQueue.add(new int[] {thisHeight, thisQueue[1], thisQueue[2], thisQueue[3]});
                            }else{
                                break;
                            }
                        }
                    }else{
                        break;
                    }
                }
            }

            if(thisQueue[2] < leftNum){
                int thisWidth = (thisQueue[1] + leftRight[2]);

                if(thisQueue[0] >= 0 && thisQueue[0] < height && thisWidth >= 0 && thisWidth < width){
                    if(!visitList[thisQueue[0]][thisWidth]){
                        if(board[thisQueue[0]][thisWidth] != 1){
                            result++;
                            visitList[thisQueue[0]][thisWidth] = true;
                            bfsQueue.add(new int[] {thisQueue[0], thisWidth, (thisQueue[2]+1), thisQueue[3]});
                        }
                    }
                }
            }

            if(thisQueue[3] < rightNum){
                int thisWidth = (thisQueue[1] + leftRight[3]);

                if(thisQueue[0] >= 0 && thisQueue[0] < height && thisWidth >= 0 && thisWidth < width){
                    if(!visitList[thisQueue[0]][thisWidth]){
                        if(board[thisQueue[0]][thisWidth] != 1){
                            result++;
                            visitList[thisQueue[0]][thisWidth] = true;
                            bfsQueue.add(new int[] {thisQueue[0], thisWidth, thisQueue[2], (thisQueue[3]+1)});
                        }
                    }
                }
            }
        }

        System.out.println(result);
    }

}

 

 

 

후기

---

위 풀이법과 같은 아이디어를 쉽게 생각해내지 못해 상당히 애먹었던 문제. 알고리즘을 생각해내는 부분이나 이를 구현하는 방식 자체는 어렵지 않으니 아마 플레티넘 5 레벨로 측정된 이유도 위 아이디어 때문일 것이라 생각한다. 여태까지 문제를 풀면서 좌우 이동 횟수로 인해 어느 한 지점에 접근하지 못하는 경우를 만난 적이 없었기 때문에 고생을 좀 했다. 다시 말해 그동안 얼마나 관성적으로 문제를 풀었는지, 풀던 방식으로만 문제를 풀었는지 반성하게 되었다. 당연하다고 생각하더라도, 왜 그렇게 되는지, 그 방법에는 어떤 맹점이 있는지 파악하는 습관을 들이도록 하자.

 

오랜만에 문제점을 알아도 해결하기 쉽지 않은 문제였다. 그래도 조금은 뿌듯...?