[BOJ] 1063. 늑대와 양(Python)

www.acmicpc.net/problem/16956

16956번: 늑대와 양

실버 4 문제인데 문제와 예시 출력을 여러 번 보면서 어떻게 하면 이런 출력이 나오는지 꽤 고민했다,,

도대체 울타리를 어디에 설치해야 하는지!

너무 막막해서 다른 블로그를 보면서 아이디어를 조금 참고했다.

페이지를 좀더 내려보니, 내가 간과한 이런 문구가 있었다.

"이 문제는 설치해야 하는 울타리의 최소 개수를 구하는 문제가 아니다."

이것이 핵심이었다. 즉, 울타리에 대한 제한 조건이 존재하지 않는다는 것이다.

문제에서 물어보는 것은 늑대와 양이 인접한 경우가 있는지 없는지였고, 맵은 어떻게 출력되든 상관이 없었다.

특별히 사용한 알고리즘은 없으며, 반복문과 조건문만으로 구현했다.

맵을 탐색하며

• 늑대 "W"를 만나면 4방향을 탐색하며 양 "S" 와 인접해 있다면, flag를 True로 만들며 불가능한 상태임을 표시한다.
• 빈 공간 "." 은 울타리 설치 가능한 공간이므로 모두 울타리를 설치한다.
• 한 행 탐색 끝났을 때 flag가 1이라면 이미 불가능하므로 0 출력
• 탐색을 마치고 flag가 여전히 False라면 인접 여부 조건에 걸린 것이 없으므로 1과 맵 상태를 출력한다. 

 

파이썬 코드는 다음과 같다.

---

import sys
input = sys.stdin.readline

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

R, C = map(int, input().split())
A = [list(input().strip()) for _ in range(R)]

flag = 0
for r in range(R):
    for c in range(C):
        if A[r][c] == "W":	 # 늑대일 때
            for d in range(4):
                nr = r + dr[d]
                nc = c + dc[d]
                if not (0 <= nr < R and 0 <= nc < C):	# 격자 밖으로 나가면
                    continue
                elif A[nr][nc] == "S":      # 늑대와 양이 인접하면 불가능
                    flag = 1
                    break
        elif A[r][c] == ".":    # 빈 공간은 모두 울타리 설치
            A[r][c] = "D"

    # 한 행 탐색 끝났을 때 flag가 1이라면 이미 불가능하므로 0 출력
    if flag:
        print(0)
        break

if not flag:
    print(1)
    for row in A:
        print(''.join(row))

---

• 시간 : 152ms / 메모리 : 133160KB
• 고찰 : 문제를 잘 읽자. 처음 읽을 때, 문제에서 원하는 것이 무엇인지 정확하게 파악하자. 대충 읽다가 이 사단이 난다.