[Python] 백준 1926 그림 - DFS

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

1926번: 그림

문제

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

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

예제 입력 1 복사

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1 복사

4
9

---

풀이

• DFS 이용한 배열 탐색
• 대각선으로 이어진 그림은 떨어진 그림 -> 상하좌우 방향벡터 이용하여 주변값 확인
• 배열에 존재하는 그림 중 가장 넓은 그림을 출력하기 위해 배열에 넓이를 저장, max() 사용하여 출력

!! 런타임 에러(ValueError) 발생

result = []

print(max(result))

그림의 넓이를 담기 위해 result 배열을 생성 -> 해당 배열의 길이 0

max() 사용 시 배열이 비어있기 때문에 런타임 에러 발생

 

해결 방법

# 1. 배열이 비어있지 않도록 0 집어넣기
result = [0]

# 2. 출력할 때 예외 조건 부여하기
if len(result) == 0:
    print(0)
    print(0)
else:
    print(cnt)
    print(max(result))

 

코드

from collections import deque

# 상하좌우 방향벡터
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 넓이 저장 배열
result = []

# 그림의 개수
cnt = 0

def Dfs(x, y):
    area = 1                # 그림의 넓이
    q = deque()
    q.append((x, y))        # 좌표 데크에 넣어 저장
    visited[x][y] = True    # 방문 처리


    while q:
        x, y = q.pop()
        # 상하좌우 탐색해서 그림이 존재하면 데크에 위치값 저장 후 그림 넓이 1 증가
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
            if board[nx][ny] == 1 and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True
                area += 1
    return area


if __name__ == "__main__":
    # r: 열, c: 행
    r, c = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(r)]     # 한줄씩 값 채워넣기
    visited = [[False] * c for _ in range(r)]                       # 방문 배열

    for i in range(r):
        for j in range(c):
            if board[i][j] == 1 and not visited[i][j]:
                result.append(Dfs(i, j))                # 그림 넓이 저장
                cnt += 1                                # 그림 개수 증가
                visited[i][j] = True                    # 방문 처리
    
    # 그림이 없을 때는 그림의 넓이를 0으로 처리
    if len(result) == 0:
        print(0)
        print(0)
    else:
        print(cnt)
        print(max(result))