[BFS/DFS/완전탐색] 1743번 - 음식물 피하기(BFS/DFS)

[백준] 1743번 - 음식물 피하기

풀이 시간: 10분 이내

(풀이1) BFS 이용

1) 문제 해결 아이디어

BFS를 이용하여 문제를 해결하였다. 

popleft()를 할 때마다 인접한 음식물의 크기(res)를 1씩 카운팅하여 상하좌우에 인접한 음식물이 없을 때까지 이를 반복하고 종료시 음식물 크기(res)를 반환한다. 

 

for문을 돌려 graph에서 음식물(1)을 발견할 때마다 해당 좌표를 시작지점으로 하여 bfs()를 호출하였고 반환 값을 음식물 크기를 저장하는 리스트(size)에 하나씩 삽입하여 최댓값을 출력하였다.

 

2) 소스코드

from collections import deque

# BFS
def bfs(x, y):
  res = 0  # 음식물 크기
  queue = deque()
  # 시작 지점 삽입, 방문 표시
  queue.append((x, y))
  graph[x][y] = 0

  while queue:
    x, y = queue.popleft()
    res += 1  # 음식물 추가
    # 상하좌우 탐색
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      # 범위 내이고 음식물이면
      if(0 <= nx < n and 0 <= ny < m):
        if(graph[nx][ny] == 1):
          # 삽입, 방문 표시
          queue.append((nx, ny))
          graph[nx][ny] = 0
  return res       

# 세로, 가로, 음식물 총 개수
n, m, k = map(int, input().split())
size = []  # 음식물 크기
graph = [[0] * m for _ in range(n)]  # n*m
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 음식물 좌표 입력받기
for _ in range(k):
  r, c = map(int, input().split())
  graph[r - 1][c - 1] = 1  # 음식물 표시


for i in range(n):
  for j in range(m):
    # 음식물이 있는 좌표에서 bfs()호출
    if(graph[i][j] == 1):
      size.append(bfs(i, j))

print(max(size))

 

(풀이2) DFS 이용

1) 문제 해결 아이디어

DFS를 이용하여 문제를 해결하였다. 

현재 지점을 방문할 때 마다 음식물의 크기(res)를 1씩 카운팅하여 상하좌우에 인접한 음식물이 있다면 해당 좌표에서 dfs()를 호출하였다. 

 

for문을 돌려 graph에서 음식물(1)을 발견할 때마다 해당 좌표를 시작지점으로 하여 dfs()를 호출하였고 전역변수로 선언된 음식물 크기(res)를 음식물 크기를 저장하는 리스트(size)에 하나씩 삽입하고 최댓값을 출력하였다. 여기서 주의해야할 점은 1번 풀이와 다르게 dfs() 호출 후 res값을 0으로 초기화해주어야 한다는 것이다.(전역변수로 선언되었기 때문에)

 

2) 소스코드

import sys
sys.setrecursionlimit(10**6)

# DFS
def dfs(x, y):
  global res
  # 현재 지점 방문 표시
  res += 1
  graph[x][y] = 0

  # 상하좌우 탐색
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    # 범위 내이고 음식물이면
    if(0 <= nx < n and 0 <= ny < m):
      if(graph[nx][ny] == 1):
        # 해당 좌표 dfs()호출
        dfs(nx, ny)
        
    
n, m, k = map(int, input().split())
graph = [[0] * m for _ in range(n)]  # n*m
size = []  # 음식물 크기
res = 0  # 음식물 크기
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 음식물 좌표 입력받기
for _ in range(k):
  r, c = map(int, input().split())
  graph[r - 1][c - 1] = 1  # 음식물 표시

for i in range(n):
  for j in range(m):
    # 음식물이 있는 좌표에서 dfs()호출
    if(graph[i][j] == 1):
      dfs(i, j)
      size.append(res)
      res = 0  # 음식물 크기 초기화

print(max(size))