[BOJ] 1926. 그림

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

1926번: 그림

 

1. 해결 방법

1. 아이디어
- 2중 for => 값 1 & 방문 x => BFS
- BFS 돌면서 그림 개수 + 1, 최댓값을 갱신

2. 시간복잡도 (한번에 2억개를 실행)
- BFS : O(V + E)
- V : m(최대 500) X n(최대 500) = 250000
- E : 대략 V X 4(넉넉히) = 4 * 250000
- O : 5 * 250000 < 2억개 => 시간복잡도 문제 없음

3. 자료구조
- 그래프 전체 지도 : int[][]
- 방문 : bool[][]
- Queue(BFS)

 이 문제의 입력은 2차원 배열로 이루어져 있다. 그렇기 때문에 배열을 다룰 때에는 2차원 배열을 사용하면 된다.

 

그리고 해당 vertex와 연관된 vertex의 관계를 확인해 나가면서 판단해야하기 때문에 자료구조 큐(Queue)를 이요한 BFS 알고리즘이라고 생각하면 된다. 

 

입력을 2차원 배열로 받기 때문에,

그래프의 전체 지도를 int[][]인 2차원 배열로 받고 큐로 vertex를 돌면서 방문했는지 하지 않았는지 판단하기 위해 False or True로 이루어진 2차원 배열도 구현해야한다.

 

2. 코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(n)]
chk = [[False] * m for _ in range(n)]

# 이동
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# 최대값 함수
def bfs(y, x):
    rs = 1
    q = deque()
    q.append((y, x))

    while q:
        ey, ex = q.popleft()
        for k in range(4):
            ny = ey + dy[k]
            nx = ex + dx[k]
            if 0 <= ny < n and 0 <= nx < m:
                if map[ny][nx] == 1 and chk[ny][nx] == False:
                    rs += 1
                    chk[ny][nx] = True
                    q.append((ny, nx))

    return rs


cnt = 0
maxv = 0
for j in range(n):
    for i in range(m):
        if map[j][i] == 1 and chk[j][i] == False:
            # 전체 그림 갯수 + 1 및 chk = True
            cnt += 1
            chk[j][i] = True
            # BFS > 그림 크기 구함 및 갱신
            maxv = max(maxv, bfs(j, i))


print(cnt)
print(maxv)