[백준/Python] 3184번 - 양

2023. 9. 9. 02:21·Algorithm/BaekJoon
import sys
input = sys.stdin.readline

r, c = map(int, input().split())
yard = [list(input().rstrip()) for _ in range(r)]
visited = [[False for _ in range(c)] for _ in range(r)]

# . 빈필드 / # 울타리 / o 양 / v 늑대
def bfs(a, b):
  stack = [(a,b)]
  sheep, wolf = 0, 0
  
  while stack:
    x, y = stack.pop()
    visited[x][y] = True
    # 양, 늑대 개수 세기
    if yard[x][y] == 'o':
      sheep += 1
    elif yard[x][y] == 'v':
      wolf += 1
    
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
      nx, ny = x + dx, y + dy
      if 0<=nx<r and 0<=ny<c and not visited[nx][ny] and yard[x][y] != '#':
        stack.append((nx, ny))
        visited[nx][ny] = True # 와 이거의 유무를 느낌...
  return sheep, wolf

survive_sheep, survive_wolf = 0, 0
for i in range(r):
  for j in range(c):
    if not visited[i][j] and yard[i][j] != '#':
      s, w = bfs(i, j)
      if s > w:
        survive_sheep += s
      else:
        survive_wolf += w

print(survive_sheep,survive_wolf)

와.. 처음 로직은 맞았는데 인접 노드 넣을 때 visited=True 이거 안넣어줘서 계속 틀렸었다.

(근데 예제 코드들은 어떻게 맞았는지 신기하다)

 

저 줄이 중요한 이유는 다음과 같다.

인접 노드들을 stack에 넣어줬는데 True를 해주지 않았다. 그럼 또 같은 노드가 인접 노드로 들어서 양, 늑대 개수가 달라질 수 있게 된다.

bfs에서는 visited 체크를 인접 노드 넣을 때 필요하다!!! 그러므로 인접 노드가 stack에 들어가면 true로 해줘야 한다!

 

고로 아래와 같이 코드를 짜도 무방하다

...
def bfs(a, b):
  stack = [(a,b)]
  visited[a][b] = True
  sheep, wolf = 0, 0
  
  while stack:
    x, y = stack.pop()
    # 양, 늑대 개수 세기
    if yard[x][y] == 'o':
      sheep += 1
    elif yard[x][y] == 'v':
      wolf += 1
...

 

다른 사람 풀이

- Queue 를 이용

- DFS를 이용

- visited를 사용하지 않고, 방문한 자리를 #로 바꿈 -> 울타리(#) 유무만 계속 체크 (시간, 메모리 부분에서 이 코드가 근소하게 효율적이라고 함)

- 처음에 양, 늑대를 카운트해주고 bfs를 돌리면서 - 해줌

'Algorithm > BaekJoon' 카테고리의 다른 글

[백준/Python] 1600번 - 말이 되고픈 원숭이  (0) 2023.09.10
[백준/Python] 13549번-숨바꼭질 3  (0) 2023.09.10
[백준/Python] 9375번 - 패션왕 신해빈  (0) 2023.09.09
[백준/Python] 2146번 - 다리 만들기  (0) 2023.09.06
[백준/Python] 2573번 - 빙산  (0) 2023.09.06
'Algorithm/BaekJoon' 카테고리의 다른 글
  • [백준/Python] 1600번 - 말이 되고픈 원숭이
  • [백준/Python] 13549번-숨바꼭질 3
  • [백준/Python] 9375번 - 패션왕 신해빈
  • [백준/Python] 2146번 - 다리 만들기
빵빵0
빵빵0
(아직은) 공부하고 정리하는 블로그입니다.
  • 빵빵0
    Hack Your World
    빵빵0
  • 전체
    오늘
    어제
    • 분류 전체보기 (92)
      • Error Handling (7)
      • Project (5)
        • MEV (2)
      • Architecture (0)
        • API (0)
        • Cache (0)
        • 사소한 고민거리 (0)
      • Computer Science (4)
        • Data Structure (2)
        • Database (1)
        • Cloud (0)
        • OS (0)
        • Infra, Network (1)
        • AI (0)
      • Language (8)
        • Go (8)
        • Rust (0)
        • Python (0)
        • Java (0)
      • Algorithm (40)
        • BaekJoon (18)
        • Programmers (7)
        • LeetCode (6)
        • NeetCode (9)
      • SW Books (9)
        • gRPC Up & Running (1)
        • System Design Interview (2)
        • 스프링 입문을 위한 자바 객체지향의 원리와 이해 (6)
        • 블록체인 해설서 (0)
        • 후니의 쉽게 쓴 CISCO 네트워킹 (0)
      • BlockChain (4)
        • Issues (0)
        • Research (4)
        • Tech (0)
      • Own (8)
        • TIR(Today I Read) (3)
        • Personal (2)
        • Novel (0)
        • Memo (3)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    blockchain
    LeetCode
    Hash Table
    EVM
    NeetCode
    KBW
    2024
    프로그래머스
    Palindrome
    ethereum
    백준
    BFS
    BEAKJOON
    Programmers
    chart
    golang
    블록체인
    Python
    Greedy
    two pointer
    MongoDB
    goroutine
    MEV
    스택
    go
    큐
    DP
    BaekJoon
    candlechart
    context
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
빵빵0
[백준/Python] 3184번 - 양
상단으로

티스토리툴바