[백준/3184] 양 | 그래프 영역 구별 하기

 

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

3184번: 양

---

알고리즘

그래프 탐색 문제인 건 알겠는데, 같은 영역을 어떻게 판단하지?가 고민이었다.

적록색약 문제에서는 bfs 함수에서 같은 색을 만나면 계속해서 q에 그 지점을 삽입하면서 탐색을 하게 만들었는데,

얘도 마찬가지다..!

 

그래서  ⭐️⭐️⭐️⭐️⭐️ bfs 함수의 q가 모두 끝나면 ⭐️한 영역⭐️에 대한 큐가 끝나는 것임..⭐️⭐️⭐️⭐️⭐️

그니까 while q 이 부분이 주변을 탐색하는 핵심이 되는 것

 

메인 함수에서는 단순히 방문하지 않은 지점을 방문하도록 if not visited[i][j] 조건을 걸고 bfs를 호출하는 것

 

전체 코드

from collections import deque

r,c = map(int, input().split())
graph = [list(input()) for _ in range(r)]

dir = [(0,-1), (0,1), (-1,0), (1,0)]
visited = [[False]*c for _ in range(r)]


def bfs(x,y) : 
    # 주변 탐색 지점 넣는 큐니까 bfs 호출마다 갱신되어야 함..
    q = deque()
    visited[x][y] = True
    q.append((x,y))

    v, o = 0, 0
    # 해당 지점이 늑대인지 양인지 확인
    if graph[x][y] == 'v' : v += 1
    elif graph[x][y] == 'o' : o += 1

    while q : 
        x, y = q.popleft()
        for dx, dy in dir : 
            nx, ny = x+dx, y+dy
        
            # "주변" 그래프 탐색
            if 0 <= nx < r and 0 <= ny < c and visited[nx][ny] == False : 
                # 그래프를 돌면서 늑대인지 양인지 확인
                # 주변에 #이 있으면,, 다른 영역이 되니까,,
                if graph[nx][ny] == '#' : continue
                elif graph[nx][ny] == 'v' : v += 1
                elif graph[nx][ny] == 'o' : o += 1

                q.append((nx,ny))
                visited[nx][ny] = True

    return v, o
                    
wolf = 0
sheep = 0

for i in range(r) : 
    for j in range(c) :

        # 애초에 main의 for문에서 같은 영역일 때만 그래프를 탐색하도록 지정해준다.
        if graph[i][j] != '#' and visited[i][j] == False :
            
            v, o = bfs(i,j)

            # 같은 영역의 탐색이 끝나고 나서
            if o > v : sheep += o
            else : wolf += v     
print(sheep, wolf)

---

알게된 점

• bfs 함수의 while q가 주변 지점을 방문하는 것. 
• 그래서 while q 안에서 q 좌표 뺴고, for dx, dy 이렇게 ㅇㅇ
• #를 기준으로 주변 영역이 설정되니까 만약 주변에 #이 발견되면 continue 
• 주변 탐색이 끗나면 방문 처리를 해줘야함😉
• dir 좌표 실수 하지말자..