[백준] [Python] 1926번 그림 - BFS

 

www.acmicpc.net/problem/1926

1926번: 그림

 

 Python

import sys

row, col = map(int, sys.stdin.readline().split())    
board =[ list(map(int, sys.stdin.readline().split())) for _ in range(row) ]

dx = [0,0,1,-1]
dy = [1,-1,0,0]
visit = [[0 for _ in range(col)] for _ in range(row)]
q = []
cnt = 0
area = 0
for a in range(row):
    for b in range(col):
        if board[a][b] == 1 and visit[a][b] == 0:
            visit[a][b] = 1
            q.append((a,b))
        
            temp_area = 1
            while (len(q) != 0):
                #print(q)
                pos = q.pop(0)
            
                for i in range(4):
                    nx = pos[0] + dx[i]
                    ny = pos[1] + dy[i]
                    if (0<=nx<row and 0<=ny<col):
                        if (visit[nx][ny] == 0 and board[nx][ny] == 1):
                            visit[nx][ny] = visit[pos[0]][pos[1]]+1
                            temp_area+=1
                            q.append((nx,ny))
                #print(i,visit)
            cnt += 1
            area = max(area, temp_area)
    
print(cnt)
print(area)

 

 

짧은 풀이

1. DFS는 스택, BFS는 큐를 이용한다
2. 방문한 적이 없는 곳부터 넓이를 1로 정하여 주변에 색칠된 곳이 있으면 한 칸씩 그 넓이를 추가한다
3. 출발점에서 구한 최대 넓이와 이전까지 구한 넓이 중 큰 넓이로 업데이트 한다.
4. 출발했다는 의미는 그 부분은 그림의 영역이며, 이전에 색칠된 적이 있으면 다음 칸으로 넘어간다. 그러므로 하단에 개수를 추가하는 식을 적었다.