[16956] 늑대와 양 in python

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

16956번: 늑대와 양

---

이 문제는 울타리의 최소 개수를 구하는 문제가 아니라는 것을 감안하면

쉽게 풀 수 있었던 문제입니다.. 흡

 

양은 이동할 능력이 없기 때문에 움직일 수 없고

늑대만이 인접한 칸을 자유롭게 넘나들수 있습니다.

 

인접한 칸이라는 뜻은 변을 공유하고 있다는 뜻과 동일함다.

 

. : 빈칸

s : 늑대

w : 양

d : 울타리

 

울타리를 어떻게든 설치해도 늑대가 양이 있는 칸으로 이동할 수 있다면?

> 0 을 출력한다.

 

울타리 설치를 통해 늑대가 양이 있는 칸으로 이동할 수 없다면?

> 1 을 출력한 뒤, 다음 줄부터 목장의 상태를 출력하도록!

 

 

울타리의 개수는 상관없으므로

늑대가 이동할 수 있는 칸중에

.인 칸을 모두 울타리로 채워주는 방식을 사용했다!

 

 

위 사진에 나와있는 목장의 상태를 울타리로 채우게 된다면

 

요론식으로 울타리를 채울 수 있게 된다.

 

---

# 1/11일
r,c=map(int,input().split())
array=[list(input()) for _ in range(r)]
# 늑대 = W, 양 = S

# 상,하,좌,우
dx=[-1,1,0,0]
dy=[0,0,-1,1]
answer=False

for x in range(r):
    for y in range(c):
        if array[x][y]=="S":
            for i in range(4):
                nx=x+dx[i]
                ny=y+dy[i]
                if 0<=nx<r and 0<=ny<c:
                    if array[nx][ny]=="W":
                        print(0)
                        exit()
                    elif array[nx][ny]==".":
                        array[nx][ny]='D'
print(1)
for i in range(r):
    temp=''
    for j in range(c):
        temp+=array[i][j]
    print(temp)

---

아래 방법은

백준 사이트에서 실행시간이 가장 빠른 코드임다..

공부하려고 코드를 뜯어보았더니

 

행 위주로 먼저 탐색을 진행하는데

만약 S와 W가 붙어있으면 즉시 프로그램 종료

 

 

그 다음으로는

zip함수를 이용해서

전치행렬을 만든다.

(행과 열을 주대각선 기준으로 서로 맞바꾼 행렬이다)

 

그리고 나서 다시 S와 W가 붙어있는 부분이 있으면

즉시 프로그램 종료

 

이렇게 전치행렬을 사용해서 행과 열을 바꿔가며 탐색해주는 이유는

탐색 시간을 줄이기 위함!

 

이때 .는 D로 모두 바꿔준다

 

from sys import stdin
input = stdin.readline

def solve():
    r, c = map(int, input().split())
    a = [input().rstrip() for _ in range(r)]
    flag = 1

    for x in range(r):
        if a[x].count('SW') > 0 or a[x].count('WS') > 0:
            flag = 0
            break

    if flag == 0:
        print(0)
        return

    b = [''.join(x) for x in zip(*a)]
    print(b)
    for x in range(c):
        if b[x].count('SW') > 0 or b[x].count('WS') > 0:
            flag = 0
            break

    if flag == 0:
        print(0)
        return
    print(1)

    for x in a:
        print(x.replace('.', 'D'))

if __name__ == '__main__':
    solve()