백준 3184 양

https://www.acmicpc.net/problem/3184

 

타임라인 & 사고 과정

7:09 AM — 초기 아이디어

BFS로 먼저 같은 영역을 구한다. 울타리 #를 기준으로 연결된 칸들을 하나의 영역으로 본다. visited 배열로 중복 탐색을 막는다. 영역을 구한 뒤, 그 영역 안에서 양/늑대 수를 센다. 영역 탐색이 끝난 다음에 한 번 더 훑어서 o/v 개수를 세려 했다. 두 일을 동시에 할 수 있나? 처음엔 “영역 → 카운트”를 분리해서 생각했는데, BFS가 어차피 모든 칸을 큐에서 꺼낼 때 다 방문하니, 그 순간에 바로 카운트하면 한 번에 끝낼 수 있을 듯.



8:01 AM — 수정된 결론

동시에 해야 했음. 같은 영역을 BFS로 확장해 나갈 때, 그때그때 o와 v를 함께 누적하는 게 맞다. 다만, 이렇게 바꾸다 보니 코드가 길고 분기(조건문) 중복이 생김 → 리팩토링 필요.



왜 “동시에 세기”가 맞나? (논리 근거)

BFS는 한 영역을 정확히 한 번씩 방문한다. “영역을 다 돈 뒤 다시 세기”는 한 영역을 사실상 두 번 훑는 셈이라 비효율. 큐에서 꺼낸 시점에 o/v를 더하면, 영역 탐색과 카운트를 O(R×C) 단일 패스로 끝낼 수 있다. 또한 “영역 내 비교(양 > 늑대면 늑대 0, 아니면 양 0)”는 그 영역의 BFS가 끝나는 시점에만 하면 된다.

from collections import deque
r,c = map(int,input().split())
graph = [input()for _ in range(r)]
visited = [[0 for _ in range(c)] for _ in range(r)]
q= deque()


def bfs():
    global o,v
    direction = [(1,0),(0,-1),(0,1),(-1,0)]
    while q:
        x,y = q.popleft()
        for dx, dy in direction:
            nx = x+ dx
            ny = y+ dy
            
            if 0<=nx<r and 0<=ny<c and not visited[nx][ny] and graph[nx][ny] != "#":
                if graph[nx][ny] == "v":
                    v+=1
                if graph[nx][ny] =="o":
                    o+=1
                q.append((nx,ny))
                visited[nx][ny]=1
    if o> v: 
        v=0
    else:
        o=0
    return (o,v)

ans_o =0
ans_v=0

for i in range(r):
    for j in range(c):
        o=0
        v=0
        if graph[i][j] == "v" and not visited[i][j]:
            v+=1
            q.append((i,j))
            visited[i][j] =1
            a,b=bfs()
            ans_o+=a
            ans_v+=b
          
        if graph[i][j] == "o" and not visited[i][j]:
            o+=1
            q.append((i,j))
            visited[i][j] =1
            a,b=bfs()
            ans_o+=a
            ans_v+=b
          
           
        if graph[i][j] == "." and not visited[i][j]:
            q.append((i,j))
            visited[i][j] =1
            a,b=bfs()
            ans_o+=a
            ans_v+=b
          
        
print(ans_o,ans_v)​