[백준 python] 1926 그림

문제

 

---

풀이

DFS를 사용하면 간단히 해결할 수 있는 문제이다.

n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

먼저 그래프의 크기와 정보를 입력받는다.

visited = [[False] * m for _ in range(n)]

dr = [1, -1, 0, 0]
dc = [0, 0, -1, 1]

방문여부를 저장해 줄 visited 변수를 선언한뒤 False로 초기화하였다.

def DFS(sr, sc):
    global tmp
    tmp += 1
    visited[sr][sc] = True
    
    for i in range(4):
        nr = sr + dr[i]
        nc = sc + dc[i]
        
        if 0 <= nr < n and  0 <= nc < m:
            if not visited[nr][nc] and graph[nr][nc] == 1:
                visited[nr][nc] = True
                DFS(nr, nc)

DFS 의 구현은 위와같다.

먼저 방문을 체크한 뒤 tmp를 1증가시켜준다. 이는 그림의 크기를 측정하기 위함이다.

이후 동서남북을 돌며 이동할 수 있는 좌표인지 확인 후 이동이 가능하다면 DFS로 다시 재귀한다.

 

for i in range(n):
    for j in range(m):
        if visited[i][j] == False and graph[i][j] == 1:
            num += 1
            tmp = 0
            DFS(i, j)
            scale = max(scale, tmp)

DFS를 호출하는 함수는 다음과 같다.

모든 좌표에 대해서 DFS호출 가능여부를 확인 후 호출한다.

DFS호출할 때마다 그림의 개수가 1증가하므로 num값을 증가시켜준다.

---

코드

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]


visited = [[False] * m for _ in range(n)]

dr = [1, -1, 0, 0]
dc = [0, 0, -1, 1]

num = 0
scale = 0
tmp = 0


def DFS(sr, sc):
    global tmp
    tmp += 1
    visited[sr][sc] = True
    
    for i in range(4):
        nr = sr + dr[i]
        nc = sc + dc[i]
        
        if 0 <= nr < n and  0 <= nc < m:
            if not visited[nr][nc] and graph[nr][nc] == 1:
                visited[nr][nc] = True
                DFS(nr, nc)
            

for i in range(n):
    for j in range(m):
        if visited[i][j] == False and graph[i][j] == 1:
            num += 1
            tmp = 0
            DFS(i, j)
            scale = max(scale, tmp)
            
            
print(num)
print(scale)