[백준 1926] 그림 - python (solved.ac - 실버 1)

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

1926번: 그림

풀이

문제를 보았을때 알수있는 힌트

0,0부터 n,m 좌표까지 한개씩 반복하여 확인하면 되며 상하좌우를 움직이며 연결되어 있으면 넚이의 수를 늘리고 새로운 넓이가 나오면 그림의 개수를 늘리는 형식으로 문제를 풀면 된다.

DFS,BFS로 풀수있는데 DFS는 메모리 초과로 풀리지 않는다.(이부분은 나중에 어려 시도를 해봐야겠다. 이미 많은 시도를 했지만 메모리초과를 해결하지 못했다.)

예상으로는 500X500 사이즈여서 메모리가 터지는 느낌이 든다. 반복은 줄이던지 중간에 컷하는 방법을 찾아내면 BFS도 풀수있지 않은까 싶다.

BFS를 통해서는 재귀함수가 아니기에 쉽게 풀리게 되었다.

 

DFS 코드(결과: 메모리 초과)

# DFS
import sys
sys.setrecursionlimit(1000000)

def dfs(x,y):
    global count
    if x<=-1 or x>=n or y<=-1 or y>=m:
        return False
    elif graph[x][y]==1:
        count+=1
        graph[x][y]=0
        for i in range(4):
            dfs(x+dx[i],y+dy[i])
        return True
    return False

dx=[-1,1,0,0]
dy=[0,0,-1,1]

input = sys.stdin.readline

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

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

for i in range(n):
    for j in range(m):
        count=0
        if dfs(i,j):
            result_count+=1
            max_count.append(count)

print(result_count)
print(max(max_count))

 

BFS(결과: 성공)

# bfs
from collections import deque
import sys

dx=[-1,1,0,0]
dy=[0,0,-1,1]

input = sys.stdin.readline

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

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


for i in range(n):
    for j in range(m):
        if graph[i][j]==1:
            queue = deque([[i,j]])
            graph[i][j]=0
            count=1
            while queue:
                # print(queue.popleft())
                x,y= queue.popleft()
                for k in range(4):
                    mx=dx[k]+x
                    my=dy[k]+y
                    if -1<mx<n and -1<my<m and graph[mx][my]==1:
                        graph[mx][my]=0
                        queue.append([mx,my])
                        count+=1
            max_count.append(count)
# print(graph)
if len(max_count)==0:
    print(0)
    print(0)
else:
    print(len(max_count))
    print(max(max_count))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1926.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리