[백준] 16956번 늑대와 양 - Python3 (애드 혹 문제, 이 문제가 정말 BFS 문제 일까?)

문제와 입출력 조건

예제 입력

 

문제 해석

재한

• 미로 찾기 문제와 비슷하다.
• 1 ≤ R, C ≤ 500 이므로 최대 250000 크기의 그래프가 생성될 수 있다.
• 시간 제한은 2초이므로 O(N^2) 이하가 적절해 보인다.
• 양(S)은 가만히 있고, 늑대(W)가 움짇인다.
• 늑대가 양을 잡아 먹는 그 순간의 지점에 울타리 D를 설치 해야 한다.
• 스페셜 저지 문제이므로 쉽게 생각하면, 모든 빈 공간에 울타리 D를 설치하면 된다.
• 늑대와 양이 붙어 있는 그래프는 어떤 수를 써도 늑대를 막을 수 없다.

---

자연어 알고리즘과 코드

1. 그래프 정보를 입력 받는다.
2. 그래프 요소에 차례 차례 접근한다.
   • if 요소 빈 공간 -> 빈 공간에 울타리를 친다.
   • if 요소가 늑대 ->  상,하,좌,우로 양 있는지 확인한다.
     • 만약, if 양이 있다. -> 0을 출력하고 즉시 종료한다.
     • 만약, if 양이 없다. -> 다음 요소로 넘어간다.
   • if 요소가 양 or 울타리 -> 다음 요소로 넘어간다.
3. 그래프를 출력한다.

import sys

input = sys.stdin.readline
r,c = map(int, input().split()) 
graph = []

for i in range(r):
    graph.append(list(input().rstrip()))

dx = [-1,1,0,0] 
dy = [0,0,-1,1]
sheep,wolf,empty,defence = ('S','W','.','D') # 가독성

for i in range(r):
    for j in range(c):
        if graph[i][j] == wolf:
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]

                if nx < 0 or ny < 0 or nx >= r or ny >= c:
                    continue
                
                if graph[nx][ny] == sheep:
                    print(0)
                    exit()
            continue

        if graph[i][j] == sheep or graph[i][j] == defence:
            continue

        graph[i][j] = defence

print(1)
[print(''.join(i)) for i in graph]

애드 혹 문제란? (백준 스페셜 저지)

특정 상황에서만 정답이 되고 일반화될 수 없는 해답을 말한다.

출처: https://jake-seo-dev.tistory.com/473 [제이크서 위키 블로그:티스토리]

---

세 줄 소감

1. 백준 스페셜 저지는 "답이 여러 가지가 될 수 있어 그 모두를 답으로 채점하는 프로그램이 들어가 있다는 뜻" 이다.

2. 한 방식으로 도전하다가 아닌 거 같으면 다른 방향으로 틀어야 한다.

3. 이 문제가 백준 BFS 문제집에 있었지만, 정말 BFS 문제인지 모르겠다.

BFS 알고리즘은 Queue 자료구조를 사용한다고 배웠다. 만약, BFS 문제라면 Queue를 사용하지 않아도 이렇게 이중 for문으로 상,하,좌,우 확인하는 것도 BFS 탐색으로 취급해야 한다. (필자는 이 문제는 BFS 탐색이 아니라고 생각한다.)