백준 16956번 : 늑대와 양

 

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

16956번: 늑대와 양

 

 DFS, BFS를 이용한 그래프탐색 카테고리에 포함된 문제들을 풀다가 특이한 문제를 발견했다.

문제를 요약하면 1x1 크기의 칸으로 나뉘어진 목장의 상태를 보고, 자유롭게 움직일 수 있는 늑대가 양에게 접근할 수 없게 울타리를 친다.

 

 문제를 보고 이해했을땐 단순히 처음 주어진 늑대의 위치 좌표를 초기 큐에 넣고 BFS 탐색을 하면서 인접한 칸들을 확인하며 인접칸에 양이 있다면 그 자리에 울타리를 설치하는 방법으로 해결하려고 했다.

늑대의 위치를 시작점으로 해서 BFS 탐색을 하다보면 늑대가 갈 수 있는 모든 칸에 방문할 것이고, 양이 있는 칸에 도달할 때마다 그 경로에 울타리를 설치하면 늑대는 양에게 접근할 수 없게 된다.

 

 그런데 입출력 예제를 보니 내가 떠올린 아이디어로는 출력될 수 없는 예제가 존재했다. 예제출력 1번과 3번이 그러했는데, 특히 3번의 경우 목장에 늑대가 존재하지 않는데도 울타리를 설치했다!!

알고리즘은 본디 효율적으로 작성하는게 정석이다. 하지만 이 문제에 나와있는 예제출력을 만들기 위해선 정반대 길을 걸어야했음을 예제만 봐도 알 수 있었다.

 

 지금까지 풀었던 문제들은 문제의 예제출력과 다르게 출력되면 오답이었기에 이번 문제도 너무도 당연히 예제처럼 출력되어야 정답이라고 생각했다. 보통은 "어떻게" 울타리를 설치해야 한다는 설명이나 지침이 문제에 나와있기 마련인데, 그런게 전혀 없어서 의아하면서도 불쾌한 기분을 갖고 예제처럼 출력할 수 있는 풀이 방법을 고민하기 시작했다.

 

 2시간을 고민하다가 이 문제의 알고리즘 분류 중에서 "구성적" 및 "애드-혹"이라는 처음보는 단어가 눈에 들어왔다.

 

 구성적은 알고리즘의 정당성을 증명하는 방법 중 하나라고 한다.

즉,  "내가 생각한 방법이 문제에서 원하는 답을 도출할 수 있는가?" 를 보여주는 방식 중 하나이다.

이 문제에서 어떤 임의의 목장 상태가 주어졌을때 "이 상태에서 늑대가 양에게 접근할 수 없게 울타리를 설치할 방법이 있는가?" 라고 내게 질문한다면 "예" 또는 "아니오"라는 답을 내야한다. 만약 "예"(또는 "아니오")라고 답했다면, 구성적 증명은 내가 낸 답에 대한 예시를 직접 보여주어 옳음을 증명하거나 답을 도출해내는 과정을 보여주는 식이다.

 

 결국 내가 옳음을 증명하려면 주어진 목장상태에서 늑대가 양에게 접근할 수 없도록 울타리를 설치해놓은 목장의 상태를 자신있게 보여주면 된다. 따라서 울타리가 설치된 상태는 여러가지 경우가 나올 수 있다. 문제에 나와있는 예제출력처럼 또는 내가 앞서 생각한 방식처럼.

아니면 울타리를 설치하는 과정을 하나하나 보여주면 된다. 마치 학창시절 선생님이 내준 문제를 칠판 앞에서 풀듯이. 그리고 그 과정을 우리는 알고리즘이라고 부르기로 했다.

 

 애드-혹. 이름보고 쫄 필요없다. 어떠한 정형화된 알고리즘(ex. BFS, DFS 등)을 써서 푸는게 문제가 아니라 그 문제만의 알고리즘을 만들어서 푸는 문제라고 한다. 풀이방법을 보면 알겠지만 이 문제는 사실 그래프 탐색문제라고 보기 조금 애매하다. 그래프 탐색 알고리즘을 사용해서 풀 순 있지만 꼭 그 알고리즘이 아니면 풀 수 없는 것은 아니다. 아마 그런 것 때문에 애드-혹 으로 분류를 한 것 같다.

 

 결론적으로 위 배운 개념들을 종합해서 정리하자면 "어떻게든" 문제에서 요구하는 조건만 맞추면 된다는 것. 울타리를 그래프 탐색을 통해 설치하던, 선형 탐색을 통해 설치하던간에 테스트 케이스(주어지는 목장 상태)마다 울타리를 설치해서 늑대가 양에게 접근할 수 없음(또는 접근 할수밖에 없음)을 증명하면 된다. 아마 온라인 저지 내부적으로 내가 제출한 답(울타리가 설치된 목장 상태)을 보고 정말로 그러한지 시뮬레이션을 돌리는게 아닌가 싶다.

 

위 과정을 거치면서 얻은 중요한 정보는 "문제의 예제출력과 달라도 정답이 될 수 있다."

 

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
farm = [list(input().rstrip()) for _ in range(r)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
flag = 0
for i in range(r):
    for j in range(c):
        if farm[i][j] == 'S':
            for k in range(4):
                px, py = i+dx[k], j+dy[k]
                if px < 0 or px > r-1 or py < 0 or py > c-1:
                    continue
                if farm[px][py] == '.':
                    farm[px][py] = 'D'
                elif farm[px][py] == 'W':
                    flag = 1
                    break
    if flag:
        print(0)
        exit(0)

print(1)
for i in range(r):
    print(''.join(farm[i]))