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

📌 알고리즘 정리

 

---

📃 문제

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

1743번: 음식물 피하기

---

✍ 풀이과정

import sys
from collections import deque

n, m, k = map(int, sys.stdin.readline().split())

board =[[0]*m for _ in range(n)]

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

# 상하좌우
dx = [-1, 1,0,0]
dy = [0, 0,-1,1]

visited = [[0]*m for _ in range(n)]

def check(x,y):
    queue = deque()
    queue.append((x, y))

    visited[x][y] = 1
    cnt=1

    while queue:
        cur_x, cur_y = queue.popleft()
        for i in range(4):
            X = cur_x + dx[i]
            Y = cur_y + dy[i]

            if 0 <= X < n and 0 <= Y < m and visited[X][Y] == 0 and board[X][Y] == 1:
                queue.append((X, Y))
                visited[X][Y] = 1
                cnt += 1
    return cnt

results=[]
for i in range(n):
    for j in range(m):
        if board[i][j] ==1: # 쓰레기인 경우
            results.append(check(i,j))
print(max(results))

이 문제는 bfs, dfs로 모두 풀 수 있는 문제이다.

나는 bfs가 더 편해서 bfs로 풀었다.

 

- 쓰레기의 위치에 대한 정보를 담고 있는 board와 방문 여부를 알려주는 visited 리스트를 생성

- for 문을 돌면서 쓰레기가 위치한 지점에서부터 탐색을 시작하는 check 함수를 생성

 * check 함수에서는 해당 지점의 상하좌우를 확인하여 쓰레기가 위치하며, 방문한 적 없는 곳을 queue에 추가한다.

---