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

참고: https://www.acmicpc.net/problem/1743

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

예제와 힌트를 보면 쉽게 이해할 수 있는데,

 

 

음식물이 떨어진 좌표가 주어지고 해당 좌표가 상하좌우로 붙은 음식물을

피해야한다. 이 중 붙은 음식물의 크기가 가장 큰 것의 크기를 출력하면 된다.

 

힌트에서 보게 되면 #으로 이루어진 것 중

상하좌우로 붙어 있는 크기 중 가장 큰 4가 제일 큰 값이 된다.

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m, k = map(int, input().split())
data = [[0] * m for _ in range(n)]
chk = [[False] * m for _ in range(n)]
cnt, temp = 1, 1

for _ in range(k):
  r, c = map(int, input().split())
  data[r-1][c-1] = 1

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
  
def dfs(y, x):
  global temp
  for k in range(4):
    ny = y + dy[k]
    nx = x + dx[k]
    if 0 <= ny < n and 0 <= nx < m:
      if data[ny][nx] and not chk[ny][nx]:
        chk[ny][nx] = True
        temp += 1
        dfs(ny, nx)
  return temp
  
for i in range(n):
  for j in range(m):
    if data[i][j] and not chk[i][j]:
      chk[i][j] = True
      cnt = max(cnt, dfs(i, j))
      temp = 1
      
print(cnt)

 

깊이 탐색으로 음식물의 크기의 최댓값을 갱신하는 형태로 코드를 구성하였다.

n과 m의 범위 즉 좌표는 1부터 시작하기 때문에 r과 c에 -1을 해준 좌표를

음식물이 떨어져 있는 위치라고 생각할 수 있고, 깊이 탐색을 진행하면서 크기를 세주게 된다.

 

cnt는 최댓값을 갱신해줄 변수로, temp는 dfs를 돌면서 각각의 음식물 크기를 저장할 임시 변수로

선언한 다음에 return되는 값과 현재 저장된 가장 큰 음식물의 크기 두 개를 비교하여

max 함수로 둘 중 더 큰 값을 cnt에 저장하면서 크기를 갱신해준다.

 

이때, 다시 깊이 탐색을 진행하면서 음식물 크기를 계산할 임시 변수 temp는

dfs가 끝난 이후에 다시 1로 초기화를 진행해주어야 중복해서 세지 않을 수 있다.

 

화이팅 💪