그림 백준 1926번 BFS

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

문제 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

전형적인 BFS문제입니다. 쭉 풀어봅시다.

n, m = map(int,input().split())
map_list = []
for i in range(n):
    map_list.append(list(map(int,input().split())))

한가지 기억하셔야 할게 우리는 x,y 좌표를 지정을 하면 x는 가로축(열)이고 y는 세로축(행)인데

자료구조에서 2차원 배열 리스트에서 x는 행이고 y는 열입니다. 이게 생각할때 무의식적으로 반대로 생각하면 코드가 꼬일 수가 있으니 충분히 기억하고 있으셔야합니다. (사실 코드는 이상이 없는데 index error뜬다 싶으면 대충 이거 반대로 지정했다는 소리입니다)

from collections import deque
dx = [1,0,-1,0]
dy = [0,1,0,-1]
vist = [[0]*m for _ in range(n)]
count = 0
mx = 0

for i in range(n):
    for j in range(m):
        if map_list[i][j] and vist[i][j]==0:
            vist[i][j]=1
            count += 1
            queue = deque()
            queue.append([i,j])
            max_num = 0
            while queue:
                max_num += 1
                curr = queue.popleft()
                for k in range(4):
                    nx = curr[0]+dx[k]
                    ny = curr[1]+dy[k]
                    if nx<0 or nx>=n or ny<0 or ny>=m:
                        continue
                    if map_list[nx][ny]!=1 or vist[nx][ny]:
                        continue
                    vist[nx][ny] = 1
                    queue.append([nx,ny]) 
            mx = max(mx,max_num) 
            
print(count)
print(mx)

결국 전체 2차원 리스트를 봐야하니 이중 for문을 사용하면 됩니다. 그런데 한가지 주의해야할게 맵만 있으면 되는게 아니라 방문도 기록을 해야 합니다.

그리고 만약 방문이 가능하고 방문을 하지 않았다면 BFS를 시작을 합니다 while부분입니다. 먼저 BFS가 시작할때는 그림을 하나 발견했다는 의미이니 count를 하나 추가를 하고 지도의 크기를 계산해야하니 max_num을 관리합시다.

4방향으로 체크를 하고 해당 칸이 범위를 벗어나거나 해당 부분을 먼저 방문했다면(먼저 방문했다면 이미 최단거리) 넘어가고 아니라면 방문처리와 함께 큐에 추가를 합니다.

그렇게 BFS가 끝나면 가장 큰 그림이었는지 확인을 하고 진행을 합니다.

마지막으로 출력하면 끝!