[BOJ][Python] 1926번 - 그림[DFS/BFS - 실버 1티어]

알고리즘 태그

[DFS/DFS 탐색]

태그 설명

BFS - 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
DFS - 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 해당 노드의 끝까지 탐색하고 목표 노드에 도달하면 멈추고 아니면 그 다음 노드의 자식노드들을 또 끝까지 탐색하는 방식의 탐색법

 

DFS, BFS 비교

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

문제

백준 문제 - 그림

링크: 그림

문제설명

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

예제 입력 

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력

4
9

탐색 문제의 경우에는 DFS 혹은 BFS를 사용하여 풀 수 있다. 다만 DFS의 경우에는 수행시간이 오래 걸릴 수 있다는 점만 인지하고 있으면 된다. 그 이유는 DFS의 경우 첫 노드의 자식노드까지 탐색이 완료될 때까지 다음 노드로 진행하지 않기 때문에 첫 노드에 대박이 나는게 아니라면 시간이 오래걸린다..

일단 나는 bfs를 통해서 문제를 풀었다. BFS는 Queue를 이용해서 푸는것이 핵심이다.

처음에는 DFS를 사용하여 풀었는데..런타임 오류가 나서 포기하고 BFS로 푼 문제다 일단 DFS를 이용해 푼 방식먼저 정리해둔다.

📃 소스코드 및 설명(DFS 메모리 초과)

import sys
sys.setrecursionlimit(10**6)
N, M = map(int,input().split())

# N x M 방문 유무 확인 행렬 생성
visited = [[False] * M for _ in range(N)]
# N줄 만큼 입력
graph = [list(map(int, input().split())) for _ in range(N)]
# 상, 하, 좌, 우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

each = 0
result = []

def dfs(x, y):
    global each
    # 범위 벗어나면 중단
    if x < 0 or x >= N or y < 0 or y >= M:
        return False
      
    # 범위 안에 있는데, 방문을 안했고, 값이 1이다면 그림으로 판단!
    if visited[x][y] == False and graph[x][y] == 1:
      # 조건식이 통과되면 그림으로 판단하고, count UP!!
      each += 1
      # 방문으로 표시
      visited[x][y] = True
      
      # 해당 번호부터 재귀로 상,하,좌,우 탐색
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        dfs(nx, ny)
        
      return True
    return False

# 열
for x in range(N):
  # 행
  for y in range(M):
    if dfs(x, y) == True:
        result.append(each)
        each = 0

if len(result)==0:
    print(len(result))
    print(0)
else:
    print(len(result))
    print(max(result))

내 코드 자체적인 문제일 수도 있을거라는 생각은 든다. 오히려 잘됬다고 판단하였다. 왜냐하면 DFS/BFS를 두번이나 풀 수 있는 기회가 생겨서 재밌게 풀었다.

📃 소스코드 및 설명(BFS 성공)

from collections import deque
N, M = map(int,input().split())

# N x N 방문 유무 확인 행렬 생성
visited = [[False] * M for _ in range(N)]
# N줄 만큼 입력
graph = [list(map(int, input().split())) for _ in range(N)]
# 상, 하, 좌, 우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

each = 0
result = []

def bfs(x, y):
  # 첫번째 들어온 좌표는 그림이므로 1로 잡아준다.
  count = 1
    # 범위 벗어나면 중단

  queue = deque()
  queue.append([x, y])  
  while queue:
    x, y = queue.popleft()
    # 상하좌우로 움직여본다
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
    # 범위 안에 있는데, 방문을 안했고, 값이 1이다면 그림으로 판단!
      if 0<=nx<N and 0<=ny<M:      
        if visited[nx][ny] == False and graph[nx][ny] == 1:
          count += 1
          visited[nx][ny] = True
          queue.append([nx, ny])
  return count
        


# 열
for x in range(N):
  # 행
  for y in range(M):
  # 현재 있는 위치가 그림이고, 방문을 안했으면? 시작!
    if graph[x][y] == 1 and visited[x][y] == False: 
      visited[x][y] = True
      pic = bfs(x,y)
      result.append(pic)


if len(result)==0:
    print(len(result))
    print(0)
else:
    print(len(result))
    print(max(result))

재귀함수는 수행시간이 오래걸린다는 점을 몸소 체험한(?) 문제였던거 같다😂