음식물 피하기 ( 1743 번 )

1743번: 음식물 피하기

 

---

🧠 알고리즘

• BFS (너비 우선 탐색, Flood Fill 방식 연결 요소 탐색 )

 

✔️ 동작 방식

• 음식물이 있는 칸 좌표를 map_list에 표시 (True)
• 모든 칸을 순회하면서, 음식물이 있는 칸을 발견하면 BFS 시작
• BFS 종료 후 현재 size와 answer(최대 음식물 크기) 비교 후 갱신
• 모든 칸을 탐색한 뒤 answer 출력

---

 

🧾 코드

import sys
from collections import deque

def _main(n, m, k):
    answer = 0
    
    map_list = [[False] * m for _ in range(n)]
    for _ in range(k):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        map_list[a - 1][b - 1] = True

    for i in range(n):
        for j in range(m):
            if map_list[i][j] == True:
                size = 1
                map_list[i][j] = False
                queue = deque([(i, j)])

                while queue:
                    x, y = queue.popleft()

                    for next_x, next_y in [(x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1)]:
                        if (0 <= next_x < n) and (0 <= next_y < m) and (map_list[next_x][next_y] == True):
                            map_list[next_x][next_y] = False
                            size += 1
                            queue.append((next_x, next_y))

                answer = max(answer, size)

    return answer
                
    
n, m, k = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, m, k))

---

 

⏱️ 시간 복잡도

for i in range(n) : 높이 만큼 순회 ( 선형 시간 복잡도 )
	for j in range(m) : 너비 만큼 순회 ( 선형 시간 복잡도 )
		# 내부 bfs 알고리즘 은 대세에 지장없음
        
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )