[백준 알고리즘] 3184번 양, 파이썬(python)

3184, 양

📁 문제 출처

3184번: 양

 

💡 생각

용어 정리

• . (점)은 빈 필드
• #는 울타리
• o는 양
• v는 늑대

 

조건 정리

• 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다.
• 양은 늑대에게 싸움을 걸 수 있다.
• 영역 안의 양의 수 > 영역 안의 늑대의 수 = 양 win, 늑대 out
• 그렇지 않다면 늑대 eat 양

 

생각하기

• 어떻게 울타리 영역을 구분해서 안에 있는 양과 늑대의 수를 count 할 것인가?
• graph[i][j] in 'ov'면 bfs함수를 실행시켜 울타리 안에 늑대와 양의 수를 카운트하여 상황에 맞춰 카운트하여 return해주기.

 

🛠 나의 코드

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(a, b):
    sheep = 0 
    wolf = 0

    queue = deque()
    queue.append((a, b))

    if graph[a][b] == 'o':
        sheep += 1
    elif graph[a][b] == 'v':
        wolf += 1

    graph[a][b] = '#'

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if  0 <= nx < r and 0 <= ny < c and graph[nx][ny] != "#":
                if graph[nx][ny] == 'o':
                    sheep += 1
                elif graph[nx][ny] == 'v':
                    wolf += 1

                graph[nx][ny] = '#'
                queue.append((nx, ny))

    if wolf >= sheep:
        return 0, wolf
    elif sheep > wolf:
        return sheep, 0




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

ts = 0 # total sheep
tw = 0 # total wolf

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

for i in range(r):
    for j in range(c):
        if graph[i][j] in 'ov':
            tempSheep, tempWolf = bfs(i, j)
            ts += tempSheep
            tw += tempWolf

print(ts, tw)

 

✔️ 배운 점 및 주의할 점

• 다른 풀이를 보면 visited 배열 만들어줘서 방문 유무를 체크하고 bfs 함수를 돌리는 코드로 작성했다. 하지만 내가 처음 문제를 봤을 때 visited 배열은 안 만들어주고 방문한 자리를 #으로 만들어줘서 방문 체크를 해야겠다고 생각했다.
• 두 코드를 비교했을 때 visited를 안 만들어줬을 때가 시간과 메모리에서 근소하게 빨랐다.
• 또한, 다른 풀이를 보면 처음에 양과 늑대를 카운트해주고 bfs함수 돌리면서 -해주는 풀이도 있다.