백준 16956 늑대와 양 (with Python)

어떤 문제?

Velog에서 처음으로 쓰는 글이라 많이 어색하고 살짝 기분이 묘하네요... ^~^
개인 블로그를 직접 만들기 전까지 꾸준히 글 올려보도록 노력하겠습니다.

오늘 제가 풀어보았던 문제는 백준 온라인 저지(이하 백준)에 있는 16956번 문제 늑대와 양 입니다.

문제는 따로 설명 드리지 않고 제가 작성한 솔루션 위주로 설명을 드리고자 합니다.
따라서 문제가 궁금하시다면 백준 홈페이지에서 읽고 오시면 좋겠습니다 ~!

내가 작성한 Solution

아직 알고리즘 능력이 많이 부족하기 때문에 코드가 효율적이지 않게 보일 수 있습니다.
코멘트 주시면 감사드리겠습니다. 그리고 조언해주신 내용을 고민할 수 있도록 하겠습니다.

시작하겠습니다.

문제에서 생각해볼 점

• 늑대가 양에게 접근하지 못하게 분리하려면 늑대와 양은 무조건 떨어져 있어야 합니다.

• 목장에 늑대만 있으면 울타리를 설치할 필요 없습니다. (목장에 양만 있는 경우도 같습니다.)

코드 구현

• 입력받은 데이터에서 양의 좌표를 q 변수에 저장합니다. 동시에 양의 마리수 & 늑대 마리수를 cntS & cntW 변수에 각각 저장합니다.

• 만약 양의 마리수가 0 이거나 혹은 늑대의 마리수가 0 이면 울타리 설치가 필요 없으니 바로 결과값을 출력합니다.

• 그렇지 않다면 함수 f()를 실행합니다.

  • 함수 f()는 양의 좌표를 하나씩 꺼내고 양의 주위에 울타리를 설치합니다.

  • 만약 양의 주위에 늑대가 있다면 바로 0을 리턴합니다.

  • 만약 양의 주위가 빈 공간이라면 울타리를 설치해줍니다.

  • 양의 주위에 울타리가 있거나 혹은 또 다른 양이 있다면 아무 처리도 하지 않습니다.

  • q가 모두 비워질때까지 양의 주위에 늑대가 없다면 울타리를 설치할 수 있다는 의미이므로 1을 리턴합니다.

  • 함수 f()의 리턴값을 활용해 결과값을 출력합니다.

def f():
    while q:
        r, c = q.pop()
        for dr, dc in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            if 0 <= r + dr < R and 0 <= c + dc < C:
                # 양의 주위에 늑대가 있는 경우
                if brd[r+dr][c+dc] == 'W':
                    return 0
                elif brd[r+dr][c+dc] == '.':
                    brd[r+dr][c+dc] = 'D'
    return 1



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

q = []
cntS = 0
cntW = 0
for r in range(R):
    for c in range(C):
        if brd[r][c] == 'S':
            cntS +=1
            q.append([r, c])
        elif brd[r][c] == 'W':
            cntW += 1

# 목장에 양들만 있거나 혹은 목장에 늑대들만 있는 경우
if cntW == 0 or cntS == 0:
    print(1)
    for i in range(R):
        print(''.join(brd[i]))
else:
    result = f()

    if result:
        print(1)
        for i in range(R):
            print(''.join(brd[i]))
    else:
        print(0)