1926번: 그림

 

 

 

 

 

풀이

 

dfs와 bfs로 풀수 있는 문제입니다.

 

dfs

...

graph[0][0] ~ graph[n-1][m-1] 까지 돌면서 방문하지 않은 곳에서 dfs를 호출합니다.

dfs 함수 안에서 재귀로 dfs가 재호출 될 때마다 도화지에 그림이 그려진곳으로 전진한 것이므로 num을 1씩 증가해줍니다.

처음에 호출한 dfs가 끝나면 num을 area안에 넣고 마지막에 출력할 수 있도록 저장하고, 그림이 연결돼있는 도화지 구역 1개를 다 탐색한 것이므로 cnt를 1 증가시킨뒤 num을 0으로 초기화 합니다.

 

마지막에 cnt를 출력하고 area에서 가장큰 값을 출력합니다. 만약 그림이 하나도 없을 경우 0을 출력합니다.

...

 

 

bfs

...

graph[0][0] ~ graph[n-1][m-1] 까지 돌면서 방문하지 않은 곳에서 bfs를 호출합니다.

 

bfs가 호출될때마다 graph[x][y] 값을 0으로 num을 1로 초기화 합니다.

 

nx, ny로 다음 노드의 위치를 특정하고 graph[nx][ny]의 값이 1일 경우 queue에 nx,ny의 값을 넣으면 도화지에 그림이 그려진곳으로 전진한 것이므로 num을 1씩 증가해줍니다.

 

queue가 비게되면 num을 area안에 넣고 마지막에 출력할 수 있도록 저장하고, 그림이 연결돼있는 도화지 구역 1개를 다 탐색한 것이므로 cnt를 1 증가시킵니다.

 

마지막에 cnt를 출력하고 area에서 가장큰 값을 출력합니다. 만약 그림이 하나도 없을 경우 0을 출력합니다.

...

 

 

 

 

 

 

파이썬 dfs

import sys
from sys import stdin
sys.setrecursionlimit(10000000)

def dfs(x, y):
    if x < 0 or x >=n or y < 0 or y >= m:
        return False
    
    if graph[x][y] == 1:
        graph[x][y] = 0
        global num
        num += 1
        
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)

        return True
    return False

n, m = map(int, input().split())

graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
area = []

num = 0
cnt = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            area.append(num)
            cnt += 1
            num = 0


print(cnt)
print(max(area) if area else 0)

 

 

 

 

 

파이썬 bfs

from collections import deque
from sys import stdin

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    graph[x][y] = 0
    num = 1

    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if (0 <= nx < n) and (0 <= ny < m) and graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = 0
                num += 1           
                
    area.append(num)
    return

n, m = map(int, input().split())
graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
area = []

cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            bfs(i, j)
            cnt += 1
            
print(cnt)
print(max(area) if area else 0)