[백준 / 파이썬] 그림 (1926)

BFS DFS 문제 중 하나인 문제

BFS DFS문제가 문제 풀이 방법은 이해했는데 내 힘으로 풀기가 너무 어려워서 계속해서 연습할 예정이다

+) 최대한 DFS, BFS 두 가지로 문제 풀이 연습하기!

 

 

📌 풀이 문제

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

1926번: 그림

 

 

🤔 DFS란 ?

DFS : 깊이 우선 탐색 (Depth-FIrst Search)

- 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
- 스택 또는 재귀함수로 구현
- 검색 속도는 BFS보다 느림
- 각 경로마다 특징을 저장해야하는 경우 사

 

 

🤔 BFS란 ?

BFS : 너비 우선 탐색 (Breadth - First Search)

- 현재 정점에 연결된 가까운 점들부터 탐색
- 큐를 이용해서 구현
- 미로 찾기 등 최단 거리 구하는 경우 사용

 

 

 

내 생각으로는 '그림' 문제는 DFS, BFS 어떤 걸로 풀어도 크게 상관이 없다고 생각한다

이제 하나하나 살펴보자

 

 

💫 정답 코드 : DFS

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(x, y):
	#범위 벗어나면 return False
    if x <= -1 or y <=-1 or x >= n or y >= k:
        return False
    
    #해당 좌표의 값이 1이라면, 그림이 있는 곳임
    if picture[x][y] == 1:
        cnt.append(1)   #그림 개수 카운트
        picture[x][y] = 0   #해당 노드 방문처리

        #상,하,좌,우 재귀적으로 탐색
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
        
    return False


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

#각각 노드들 입력받아 그래프 만들어주기
picture = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

cnt = []    #총 그림 갯수 count
res = []    #각 구역의 연결된 그림 크기


for i in range(n):
    for j in range(k):
        if picture[i][j] == 1: 
            dfs(i, j)
            res.append(len(cnt))
            cnt = []

#그림 개수 출력
print(len(res))
                
 #그림 개수 있으면 가장 큰 값 출력. 아니라면 0 출력
if len(res):
    print(max(res))
else:
    print(0)

 

 

💫 정답 코드 : BFS

import sys
from collections import deque
 
n, m = map(int, input().split())
picture = []
 
picture = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    
 
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
 
def bfs(picture, a, b):
    queue = deque() #queue 만들기
    queue.append((a, b))    #queue에 (a,b) 좌표 추가해주기
    picture[a][b] = 0     #방문한 좌표 0으로 만들어주기
    count = 1   #그림 넓이 구하기 위해 count
 
    while queue:
        x, y = queue.popleft()  #queue에 있는 것 pop
        for i in range(4):  #네 방향 돌면서 각각 좌표 구하기
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:  #범위 벗어난다면 무시
                continue
            if picture[nx][ny] == 1:  #1이라면 (그림이 있는 부분이라면)
                picture[nx][ny] = 0   #방문했으니까 1-> 0
                queue.append((nx, ny))  #방문할 좌표 추가해주기
                count += 1  #넓이 구하기 위한 count
    return count
 
res = []
for i in range(n):
    for j in range(m):
        if picture[i][j] == 1:    #해당 좌표 값이 1일 때 bfs 탐색
            res.append(bfs(picture, i, j))
 
 #그림 개수 있으면 가장 큰 값 출력. 아니라면 0 출력
if len(res) == 0:
    print(len(res))
    print(0)
else:
    print(len(res))
    print(max(res))

 

 

 

아래가 DFS, 위에가 BFS 코드이다.

꽤나 큰 메모리와 시간 차이가 나는 것으로 보인다.

문제별로 적절히 BFS와 DFS를 사용하고 문제 풀이 전에 시간복잡도에 대해 간단히 계산해보고 코드를 작성해야겠다고 다시한번 느꼈다..~