[백준 알고리즘] 3184번 양, 파이썬(python)
글 작성자: 망고좋아
반응형
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함수 돌리면서
-
해주는 풀이도 있다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 알고리즘] 11725번 트리의 부모 찾기, 파이썬(python) (0) | 2021.08.26 |
---|---|
[백준 알고리즘] 10026번 적록색약, 파이썬(python) (0) | 2021.08.25 |
[백준 알고리즘] 2468번 안전 영역, 파이썬(python) (0) | 2021.08.25 |
[백준 알고리즘] 2583번 영역 구하기, 파이썬(python) (0) | 2021.08.24 |
[백준 알고리즘] 7562번 나이트의 이동, 파이썬(python) (0) | 2021.08.24 |
댓글
이 글 공유하기
다른 글
-
[백준 알고리즘] 11725번 트리의 부모 찾기, 파이썬(python)
[백준 알고리즘] 11725번 트리의 부모 찾기, 파이썬(python)
2021.08.26 -
[백준 알고리즘] 10026번 적록색약, 파이썬(python)
[백준 알고리즘] 10026번 적록색약, 파이썬(python)
2021.08.25 -
[백준 알고리즘] 2468번 안전 영역, 파이썬(python)
[백준 알고리즘] 2468번 안전 영역, 파이썬(python)
2021.08.25 -
[백준 알고리즘] 2583번 영역 구하기, 파이썬(python)
[백준 알고리즘] 2583번 영역 구하기, 파이썬(python)
2021.08.24