[백준(Python)] 1926번 : 그림

문제

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

1926번: 그림

 

코드

• DFS

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

dy = [0,1,0,-1]
dx = [1,0,-1,0]

def dfs(y, x):  # DFS 함수 정의
    global each # 전역변수
    each += 1
    
    for k in range(4):  # 다음 4방향의 값 확인 up, right, down, left
        ny = y + dy[k]
        nx = x + dx[k]
        
        if 0<=ny<n and 0<=nx<m and map[ny][nx] == 1 and chk[ny][nx] == False:   
            # map 사이즈 내에서 next값이 1이면서 미방문일 때 
            chk[ny][nx] = True  # 방문 처리
            dfs(ny, nx) # 재귀

for j in range(n):
    for i in range(m):
        if map[j][i] == 1 and chk[j][i] == False: # 1이면서 방문하지 않은 경우
            chk[j][i] = True    #방문 처리
            each = 0    # each값 초기화
            dfs(j, i)   # DFS를 이용해서 크기 구하기
            result.append(each)

if len(result) == 0 :
    print(len(result))
    print(0)
else:
    print(len(result))
    print(max(result))

 

 

• BFS

from collections import deque
import sys
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)]

dy = [0,1,0,-1]
dx = [1,0,-1,0]

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:
            chk[j][i] = True
            cnt += 1
            maxv = max(maxv, bfs(j,i))

print(cnt)
print(maxv)

---

해설

• DFS & BFS를 연습하기 좋은 문제.
• BFS가 더 효율적인 문제.
  • 가장 넓은 그림의 넓이 => BFS가 더 효율적인 것을 알 수 있음.