백준 알고리즘 14145번 Žetva(python)

기본적인 DFS & BFS 문제이다.

처음에 그래프를 생성할 때 graph = [map(int, list(input())) for _ in range(R)] 와 같은 방식으로

생성해서 계속 메모리 초과가 나왔다. graph = [list(input()) for _ in range(R)] 로 하면 통과된다. 

DFS 풀이

import sys
from copy import deepcopy
sys.setrecursionlimit(30000000)

def dfs_check(y, x, cnt):
    a[y][x] = '0'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < R) and (0 <= X < S) and a[Y][X] == '1':
            cnt = dfs_check(Y, X, cnt+1)
    return cnt

def dfs(y, x, n):
    graph[y][x] = n
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < R) and (0 <= X < S) and graph[Y][X] == '1':
            dfs(Y, X, n)

R, S = map(int, input().split())
graph = [list(input()) for _ in range(R)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
li = []
a = deepcopy(graph)
for i in range(R):
    for j in range(S):
        if a[i][j] == '1':
            li.append((i, j, dfs_check(i, j, 1)))
li.sort(key=lambda x:x[2])
for i in range(len(li)):
    dfs(li[i][0], li[i][1], i+1)
for line in graph:
    print(''.join(map(str, line)))

BFS 풀이

from collections import deque
from copy import deepcopy

def bfs_check(i, j):
    q = deque()
    q.append((i, j))
    a[i][j] = '0'
    cnt = 0
    while q:
        y, x = q.popleft()
        cnt += 1
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < S) and a[Y][X] == '1':
                a[Y][X] = '0'
                q.append((Y, X))
    return i, j, cnt

def bfs(y, x, n):
    q = deque()
    q.append((y, x))
    graph[y][x] = n
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < S) and graph[Y][X] == '1':
                graph[Y][X] = n
                q.append((Y, X))

R, S = map(int, input().split())
graph = [list(input()) for _ in range(R)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
li = []
a = deepcopy(graph)
for i in range(R):
    for j in range(S):
        if a[i][j] == '1':
            li.append(bfs_check(i, j))
li.sort(key=lambda x:x[2])
for i in range(len(li)):
    bfs(li[i][0], li[i][1], i+1)
for line in graph:
    print(''.join(map(str, line)))