[BOJ] 1926번: 그림 (DFS)

 

문제 링크

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

 

 

 

TIL

if 0<=ny<n and 0<=nx<m and grid[ny][nx] == 1 and not visited[ny][nx]:

stack.append((ny,nx))

visited[ny][nx] = True

• stack안에 추가하는 부분에도 visited 처리 필수!!!!!! >> 그렇지 않으면 stack에는 들어갔지만 아직 처리되지 못한 좌표들이 중복 처리됨

• Python ValueError
  • 빈리스트에서 max 값을 찾는것과 같이 처리할 수 없는 매개값이 넘어왔을 때 발생
  • 따라서 위와 같이 dfs 한 것 중에서 최대값 찾는 문제에서는 빈 리스트를 처리하는 코드 필수 
    • print(max(picture) if cnt != 0 else 0)  >> 이런 처리 필요
  • 문제에서도 "그림이 하나도 없는 경우 가장 넓은 그림의 넓이는 0이다" 라고 명시되어 있음

 

 

Code

n , m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]

def dfs(i, j):
    stack = [(i,j)]
    directions = [(0,1), (1,0), (-1,0), (0,-1)]

    area = 0
    while stack:
        cy, cx = stack.pop()
        visited[cy][cx] = True
        area += 1

        for dy, dx in directions:
            ny, nx = cy+dy, cx+dx
            if 0<=ny<n and 0<=nx<m and grid[ny][nx] == 1 and not visited[ny][nx]:
                stack.append((ny,nx))
                visited[ny][nx] = True
    return area

picture = []
cnt = 0
for i in range(n):
    for j in range(m):
        if not visited[i][j] and grid[i][j] == 1:
            picture.append(dfs(i,j))
            cnt += 1

print(cnt)
print(max(picture) if cnt != 0 else 0)