애드혹 문제는 보기 드문 유형의 문제인데, 접할 때마다 약간 당황스럽게 만드는 문제인 듯 하다.
왜냐면, 애드혹은 정형화된 알고리즘을 쓰는 문제가 아니라, 문제의 목적에 따라 어떻게 풀어야 할지 발상을 해내는게 절반 이상이기 때문이다.
애드혹은 코드포스에서 많이 보이는 유형인데, 애드혹과 친해질 필요가 있다.

일단 먼저 쉬운 애드혹 문제부터 풀이를 해볼까 한다.

BOJ 16956 - 늑대와 양 링크
(2022.09.27 기준 S3)
(치팅하면 울타리에 갇힘)

문제

늑대가 양이 있는 칸으로 갈 수 없도록 울타리를 설치

알고리즘

울타리의 개수는 상관이 없다. 그저 늑대와 양이 만나지 않게끔만 하면 되기 때문.
그러므로 울타리를 어떻게 설치할지 잘 생각해서 늑대와 양의 위치에 따른 답을 출력하면 된다. (애드혹)
굳이 표현하면 구현..?

풀이

울타리는 어떻게 설치해도 상관이 없다고 문제에 적혀 있다.
그러므로 울타리를 양 주위에 설치를 하든, 늑대 주위에 설치를 하든, 빈 곳을 전부 울타리를 채우든 상관이 없다. 그러므로 그냥 편하게 빈 곳을 전부 울타리를 채울 것이다.
근데 만약에 빈 곳을 전부 울타리를 채웠는데도 늑대가 양한테 갈 수 있다면..?
바로 늑대가 양이랑 붙어있는 경우다. 그래서 이 경우를 찾으면 0을 출력하고 프로그램 종료하면 된다.

먼저 목장을 입력 받아 탐색을 하여 늑대들을 찾자. 늑대를 찾으면 그 위치에서 상하좌우를 검사하자. 만약 검사한 곳에 양이 있다면? 붙어있는 것이므로 0을 출력 후 프로그램 종료를 하자.

프로그램 종료가 되지 않고 탐색이 끝났다면, 모든 늑대는 양과 붙어있지 않다는 것이다. 그러면 1을 출력 후, 입력받은 목장을 빈 곳을 전부 울타리로 채워서 출력하면 된다.

코드

import sys; input = sys.stdin.readline

R, C = map(int, input().split())
matrix = [input().strip() for _ in range(R)] # 목장

# 울타리는 어떻게 설치해도 상관없으므로 빈 곳을 울타리로 다 채워도 상관이 없다.
# 이렇게 했는데도 늑대가 양으로 갈 수 있는 경우는 붙어있는 경우 뿐이다.
# 그러므로 늑대를 발견하면 상하좌우를 검사하자.
# 검사한 곳에 양이 있으면 0을 출력 후 프로그램 종료를 하자.
for r in range(R):
    for c in range(C):
        if matrix[r][c] == 'W': # 늑대일 경우
            for rr, cc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]: # 상하좌우
                if 0 <= rr < R and 0 <= cc < C: # 목장 범위 안이어야 한다.
                    if matrix[rr][cc] == 'S': # 양이면
                        print(0) # 0 출력 후 프로그램 종료
                        exit()

# 프로그램이 종료가 되지 않았다면
# 모든 늑대가 양이랑 붙어있지 않다는 것이다.
# 1 출력 후 빈 곳을 울타리로 바꿔서 출력하자.
print(1)
for r in range(R):
    print(matrix[r].replace('.', 'D'))

여담

양고기를 먹은지 정말 오래된 것 같다. 작년에 먹었나..?
오늘 여자친구한테 조만간 양고기 먹으러 가자고 말해봐야 겠다. :)
(양들아 미안)