파이썬 알고리즘 188번 | [백준 1926번] 그림 - DFS

188. 그림

1) 어떤 전략(알고리즘)으로 해결?

• dfs, bfs

2) 코딩 설명

• 1 발견하면 이어져있는 아이들 탐색

<내 풀이>

• bfs로 접근해서 재귀가 아닌 큐가 있는 동안 돌게 해주었더니 잘 통과가 됐다.

from collections import deque
import sys
sys.setrecursionlimit(10**6)

n,m = map(int, sys.stdin.readline().rstrip().split())
map = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]

cnt = 0 # 그림의 갯수

rdis = [ 1, -1, 0, 0]
cdis = [0, 0 , 1, -1]

def bfs(q) :
    global big
    while q : 
        now = q.popleft()
        for i in range(4) :
            tmpr = now[0]+rdis[i]
            tmpc = now[1]+cdis[i]

            if 0<=tmpr<n and \
                0<=tmpc<m and \
                    visited[tmpr][tmpc]==0 and \
                        map[tmpr][tmpc]==1 : 
                # 범위에서 안 벗어나고 , 안 방문했고, 1이라면
                big+=1 # 그림 크기 증가시키기 
                visited[tmpr][tmpc] = 1
                q.append((tmpr,tmpc))
    return big

maxarea = 0 # 넓은 그림의 넓이
q=deque()
for i in range(n) :
    for j in range(m) :
        if(map[i][j]==1 and visited[i][j]==0) :
            q.append((i,j)) # 큐에 해당 좌표 집어넣어 
            cnt+=1 # 그림 발견 (그림 갯수 갱신)
            big = 1 # 그림의 크기 
            visited[i][j] = 1
            maxarea = max(maxarea, bfs(q)) # 기존 큰 그림 vs 지금 그림 크기 

print(cnt)
print(maxarea)

<내 틀렸던 풀이, 문제점>

메모리초과 및 recursion 에러 (DFS)

• 다들 dfs 로는 통과를 못하고 bfs 로 풀어야 통과가 된대서 수정

import sys

n,m = map(int, sys.stdin.readline().rstrip().split())
map = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
cnt = 0 # 그림의 갯수
rdis = [ 1, -1, 0, 0]
cdis = [0, 0 , 1, -1]

def dfs(r,c) :
    global visited, big

    for i in range(4) :
        tmpr = r+rdis[i]
        tmpc = c+cdis[i]

        if 0<=tmpr<n and \
            0<=tmpc<m and \
                visited[tmpr][tmpc]==0 and \
                    map[tmpr][tmpc]==1 :

            big+=1
            visited[tmpr][tmpc] = 1
            dfs(tmpr,tmpc)

maxarea = 0 # 넓은 그림의 넓이

for i in range(n) :
    for j in range(m) :
        if(map[i][j]==1 and visited[i][j]==0) :
            cnt+=1 #그림 발견 (그림 갯수 갱신)
            big = 1
            visited[i][j] = 1
            dfs(i,j)
            if big > maxarea :
                maxarea = big

print(cnt)
print(maxarea)

bfs도 61%에서 메모리 초과;

from collections import deque
import sys
sys.setrecursionlimit(10**6)

n,m = map(int, sys.stdin.readline().rstrip().split())
map = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
cnt = 0 # 그림의 갯수
rdis = [ 1, -1, 0, 0]
cdis = [0, 0 , 1, -1]

def bfs(q) :
    global big
    while q : 
        now = q.popleft()
        for i in range(4) :
            tmpr = now[0]+rdis[i]
            tmpc = now[1]+cdis[i]

            if 0<=tmpr<n and \
                0<=tmpc<m and \
                    visited[tmpr][tmpc]==0 and \
                        map[tmpr][tmpc]==1 :
                big+=1
                visited[tmpr][tmpc] = 1
                q.append((tmpr,tmpc))
                bfs(q)

maxarea = 0 # 넓은 그림의 넓이
q = deque()
for i in range(n) :
    for j in range(m) :
        if(map[i][j]==1 and visited[i][j]==0) :
            q.append((i,j))
            cnt+=1 #그림 발견 (그림 갯수 갱신)
            big = 1
            visited[i][j] = 1
            bfs(q)
            if big > maxarea :
                maxarea = big

print(cnt)
print(maxarea)

61%,,

from collections import deque
import sys
sys.setrecursionlimit(10**6)

n,m = map(int, sys.stdin.readline().rstrip().split())
map = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]

cnt = 0 # 그림의 갯수
rdis = [ 1, -1, 0, 0]
cdis = [0, 0 , 1, -1]

def bfs(q) :
    global big
    while q : 
        now = q.popleft()

        for i in range(4) :
            tmpr = now[0]+rdis[i]
            tmpc = now[1]+cdis[i]

            if 0<=tmpr<n and \
                0<=tmpc<m and \
                    visited[tmpr][tmpc]==0 and \
                        map[tmpr][tmpc]==1 :
                big+=1
                visited[tmpr][tmpc] = 1
                q.append((tmpr,tmpc))
                bfs(q)
            else : continue
        else : return big
    return big

maxarea = 0 # 넓은 그림의 넓이
q=deque()

for i in range(n) :
    for j in range(m) :
        if(map[i][j]==1 and visited[i][j]==0) :
            q.append((i,j))
            cnt+=1 #그림 발견 (그림 갯수 갱신)
            big = 1
            visited[i][j] = 1
            maxarea = max(maxarea, bfs(q))

print(cnt)
print(maxarea)

<반성 점>

• dfs로 메모리초과 나면 bfs로 접근해보자

<배운 점>