[Python] 백준 1926 그림

 

문제 분석

• 그림의 넓이가 가장 넓은 것의 넓이 출력
• 1로 연결되어 있는 것을 한 그림
• 가로 세로로 연결된 것만 연결, 대각선은 연결 x

 

코드 설계

• bfs : 넓이 우선 탐색
• 그래프를 돌다가 1을 만나면 해당 위치에 속하는 그림의 크기 탐색
• 주변의 1 탐색 - 1이 있으면 해당 넓이 +1

 

정답 코드

1차 - 실패

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

n, m = map(int, input().split()) # n : 세로, m : 가로
g = []
d = deque()

for i in range(n) :
    g.append(list(map(int, input().split())))
visited = [[False] * m for _ in range(n)]

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

num = 0 # 그림의 개수
area = 0
max_area =0

# 1을 찾으면 bfs 시작
for i in range(n) :
    for j in range(m) :
        if g[i][j] == 1 and not visited[i][j]:
            d.append((i,j,1)) # 그림 시작 위치 & 크기
            visited[i][j] = True
            num += 1

            while d :
                h, w, area = d.popleft()
                print(h, w, area)

                # 상하좌우 이동하려고 하는데
                # 해당 위치의 값이 1이고, 아직 방문하지 않았고 (체크x), 범위를 벗어나지 않으면 이동
                # 이동할 수 없는 위치면 continue
                for k in range(4):
                    nh = h + dh[k]
                    nw = w + dw[k]

                    if nh < 0 or nh >= n or nw < 0 or nw >= m :
                        continue
                    if visited[nh][nw] : # true이면 이미 방문한 곳
                        continue
                    if g[nh][nw] != 1 :
                        continue

                    # 이동할 수 있는 조건이면
                    area += 1  # 그림의 길이 +1
                    d.append((nh, nw, area))
                    visited[nh][nw] = True

            # 해당 1이 시작하는 곳에서 넓이를 다 구했으면
            max_area = max(area, max_area)

print(num)
print(max_area)

• 그림의 최대 넓이를 제대로 구하지 못함
• area를 append 하기 전에 증가하고 덱에 넣으니까
• 나중에 뺐을 때 이미 다른곳도 탐색해서 area가 증가했는데 그때의 area 값을 다시 pop해서 반영이 안됨

 

2차 - 성공

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

n, m = map(int, input().split()) # n : 세로, m : 가로
g = []
d = deque()

for i in range(n) :
    g.append(list(map(int, input().split())))
visited = [[False] * m for _ in range(n)]

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

num = 0 # 그림의 개수
max_area =0

# 1을 찾으면 bfs 시작
for i in range(n) :
    for j in range(m) :
        if g[i][j] == 1 and not visited[i][j]:
            d.append((i,j)) # 그림 시작 위치 & 크기
            visited[i][j] = True
            area = 0
            num += 1

            while d :
                h, w, = d.popleft()
                area += 1

                # 상하좌우 이동하려고 하는데
                # 해당 위치의 값이 1이고, 아직 방문하지 않았고 (체크x), 범위를 벗어나지 않으면 이동
                # 이동할 수 없는 위치면 continue
                for k in range(4):
                    nh = h + dh[k]
                    nw = w + dw[k]

                    if nh < 0 or nh >= n or nw < 0 or nw >= m :
                        continue
                    if visited[nh][nw] : # true이면 이미 방문한 곳
                        continue
                    if g[nh][nw] != 1 :
                        continue

                    # 이동할 수 있는 조건이면
                    d.append((nh, nw))
                    visited[nh][nw] = True

            # 해당 1이 시작하는 곳에서 넓이를 다 구했으면
            max_area = max(area, max_area)

print(num)
print(max_area)