(백준) 1926.그림 / with.BFS

문제링크: https://www.acmicpc.net/problem/1926

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().rstrip().split())
draw = []
for _ in range(n):
    a = list(map(int, sys.stdin.readline().rstrip().split()))
    draw.append(a)

cnt = 0 # 그림 개수
res = [0] # 그림 넓이를 저장할 리스트

def bfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque()
    queue.append([x, y]) # 0, 0
    draw[x][y] = 0 # 방문한 노드는 0으로 초기화
    b = 1 # 넓이를 계산하기 위한 변수
    while queue: # queue 안에 원소가 있을 때 까지
        c, d = queue.popleft() # c에 0, d에 0
        for i in range (4): # i가 1일 때
            nx = c + dx[i] # 0 + 0
            ny = d + dy[i] # 0 + 0
            if (0 <= nx < n) and (0 <= ny < m) and (draw[nx][ny] == 1):
                b += 1
                draw[nx][ny] = 0
                queue.append([nx, ny])
    res.append(b)

for x in range (n):
    for y in range (m):
        if draw[x][y] == 1: # draw 안에 1이 있을 때만
            bfs(x, y) # bfs 함수를 호출하고
            cnt += 1 # 그림의 개수를 +1씩 증가

print(cnt)
print(max(res))

풀이

1. 입력값 n은 행의 개수, m은 열의 개수를 의미한다.
   1. map() 함수를 씌워서 int로 받고 공백을 기준으로 n과 m에 각각 매핑(적용)시켜준다.
2. 그림을 2차원 배열로 입력 받는다.
3. 그림 개수를 담을 cnt와 각각의 그림 넓이를 저장할 리스트 res를 선언한다.
   1. 출력값이 n*m 안에 있는 그림의 개수와 그 그림들 중 가장 넓은 넓이인걸 출력해야 되기 때문이다.
4. draw의 원소를 보기 위해 이중 반복문을 돌아서,
   1. 만약 draw의 값이 1이라면(그림이 그려져있다는 의미이니) 함수 bfs를 호출하고, 그림의 개수를 세기 위해 cnt를 1 증가한다.
5. bfs 함수는 아래와 같이 동작한다.
   1. 좌우를 살펴보기 위한 dx 리스트와
   2. 상하를 살펴보기 위한 dy 리스트를 선언한다.
   3. while문을 돌리기 위해 queue에 현재 위치 x, y값을 넣는다.
   4. 이 때 0, 0은 이제 방문한 노드니까 0으로 초기화 한다.
      1. 그림 범위 (n*m)내에서 1이 있으면 bfs 함수를 호출하기 때문이다.
   5. 각 그림의 넓이를 구하기 위해 변수 b를 1로 초기화 한다. 넓이는 queue 안에 원소가 존재하는한 1씩 증가하는 방식으로 구할 것이다. 이는 뒤에서 설명..
   6. queue 안에 원소가 있을 때까지 반복문을 돈다.
      1. c에는 현재 원소의 x 좌표값을, d에는 현재 원소의 y 좌표값을 넣는다.
      2. 현재 위치 기준 상 하 좌 우의 원소를 모두 돌아봐야 하기에 4번의 반복문을 돈다.
         1. nx로는 c 기준 상, 하를 이동하고
         2. ny로는 d 기준 좌, 우를 움직인다.
         3. 이 때 만약 nx가 n을 초과하지 않으면서 0을 포함한 양의 정수고, ny는 m을 초과하지 않으면서 0을 포함한 양의 정수이며, nx와 ny 좌표 값의 원소가 1이라면,
            1. 넓이 b를 1만큼 증가하고,
            2. 현재의 위치 (nx, ny)는 0으로 초기화하고
            3. 이 값을 queue에 넣는다.

         왜?? (아마 여기가 이 문제의 핵심 부분이라 생각함.)

         예를 들어 draw의 값이 [[111], [111]] 과 같다고 하자.

         • (0, 1), (1, 0)는 모두 유효하므로 큐에 넣고, draw[0][1]과 draw[1][0]을 0으로 설정한다.
         • 이제 큐에 [(0, 1), (1, 0)] 이 들어가 있고, 이 값을 다시 큐에서 하나씩 꺼내면서 주변 (상하좌우)를 탐색한다. 큐는 FIFO(선입선출) 이기에 (0, 1)이 먼저 빠져 나온다.
         • 그렇담 (0, 1)에선 0, 2와 1, 1이 유효하므로 큐에 넣고, draw[0][2]와 draw[1][1]을 0으로 설정한다. 이런 방식으로 계속해서 큐에 주변의 좌표를 넣고, 그 주변을 탐색하면서 그림의 넓이를 구하는 것이다. 이가 바로 BFS!
   7. 그러다 queue 안이 다 비었다면, (주변에 1이 없어서 탐색을 끝냈다면) 넓이 b값을 res에 저장한다. 왜? 그림들 중에 가장 큰 넓이를 가진 값만 출력하기 위해서.
6. 그러고 output에 맞게 cnt와 max(res) 를 print하면 끝.

질문

• Q1. 다른 분들 코드를 보니 DFS로 푸시는 분들이 계시던데, DFS로 구현하든 BFS로 구현하든 로직상 별차이가 없는 것 같다. 왜지?
  • BFS는 너비우선탐색으로 queue를 이용해서 인접한 노드를 “넓게” 탐색한다. 즉 모든 노드를 한층씩 확장해가며 탐색한다. 반대로 DFS는 stack을 이용해서 “한 방향”으로 깊게 탐색하다가 더 이상 갈 곳이 없으면 돌아가서 다른 방향으로 탐색한다. 결국 이 문제에서 BFS와 DFS의 차이는 탐색 순서 차이 뿐이라 할 수 있다.
• Q2. BFS 코드를 보면 항상 queue의 원리를 사용하던데, 왜 굳이 deque 라이브러리를 불러오는 것인가?
  • 시간복잡도 때문이다. 파이썬에서 일반적인 list를 큐처럼 사용하면, pop(0)을 이용해 큐의 앞쪽에서 값을 빼는데, pop(0)은 O(n) 시간이 걸린다. 반면, deque는 앞과 뒤에서 원소를 추가하거나 제거하는데 O(1)의 시간이 걸린다. 그래서 BFS를 구현할 때 deque를 사용한 것.

cf. 질문은 인간이하고 답변은 지피티의 답변입니다. 틀렸다면 언제든 알려주세요.

내가그린기린그림~

무서운 BFS 뇨속을 미루고 미루다 만났따 ㅎ