[Python] 3184번 양

✏️ 문제

 

문제 파악

graph 2차원 배열에 1을 양, 2를 늑대로 표시했다.

• 1 → 양
• 2 → 늑대

그리고 visited 2차원 배열의 값을 세 가지로 나눠서 대입하고 이를 이용해 조건문을 구분하였다.

• 0 → 방문 안한 필드
• 1 → 방문한 필드
• -1 → 울타리 부분으로 방문하면 안되는 필드

또한 이 문제의 경우 가로, 세로로 연결되어 있는 필드는 같은 영역이므로 방향 배열을 다음과 같이 구성했다.

d = [(1, 0), (0, 1), (-1, 0), (0, -1)]

 

BFS를 돈 후에 배열을 return 했는데 인덱스 0에는 양의 수, 인덱스 1에는 늑대의 수로 하였다.

그리고 return 된 값에서 if 문을 돌아

• 양의 수가 많으면 늑대를 우리에서 쫓아내므로 늑대의 수가 0이라 인덱스 1을 0으로 바꾸고 출력할 num 배열에 더함
• 양의 수가 작거나 같으면 양이 모두 잡아먹히므로 양의 수가 0이라 인덱스 0을 0으로 바꾸고 출력할 num 배열에 더함

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

from collections import deque
import sys

r, c = map(int, input().split())
graph = [[0] * c for _ in range(r)]
visited = [[0] * c for _ in range(r)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
num = [0, 0]

for i in range(r):
  s = input()
  for j in range(c):
    if s[j] == 'o':   # 양
      graph[i][j] = 1
    elif s[j] == 'v': # 늑대
      graph[i][j] = 2
    elif s[j] == '#': # 울타리
      visited[i][j] = -1

def bfs(x, y):
  q = deque([(x, y)])
  visited[x][y] = 1
  cnt = [0, 0]

  if graph[x][y] == 1:
    cnt[0] += 1
  if graph[x][y] == 2:
    cnt[1] += 1
  
  while q:
    x, y = q.popleft() 

    for i in range(4):
      dx = x + d[i][0]
      dy = y + d[i][1]

      if 0 <= dx < r and 0 <= dy < c and visited[dx][dy] == 0: 
        if graph[dx][dy] == 1:
          cnt[0] += 1
        if graph[dx][dy] == 2:
          cnt[1] += 1
        visited[dx][dy] = 1
        q.append([dx, dy])
  
  return cnt

for i in range(r):
  for j in range(c):
    if visited[i][j] == 0:
      temp = bfs(i, j)
      if temp[0] > temp[1]:
        temp[1] = 0
      else: 
        temp[0] = 0
      num[0] += temp[0]
      num[1] += temp[1]

for i in range(2):
  print(num[i], end=' ')

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS