[백준][Python] 1743 음식물 피하기

그래프, bfs / 실버 1

🍱

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

1743번: 음식물 피하기

 

내 풀이

from collections import deque

def bfs(x, y):
    size = 0 # 현재 음식물의 크기
    visited[x][y] = True
    q = deque()

    if arr[x][y] == 1: # 음식물인 경우
        q.append((x,y))
        size += 1
    
    while q:
        cx, cy = q.popleft()

        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]

            if nx < 0 or nx >= N or ny < 0 or ny >= M or visited[nx][ny]: # 범위를 벗어났거나 이미 방문한 곳인 경우
                continue

            visited[nx][ny] = True

            if arr[nx][ny] == 1: # 음식물인 경우
                size += 1
                q.append((nx, ny))

    return size


N, M, K = map(int, input().split())

arr = [[0] * M for _ in range(N)]
visited = [[False] * M for _ in range(N)]
food_waste = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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

for i in range(N):
    for j in range(M):
        if not visited[i][j]: # 방문하지 않은 곳
            food_waste = max(food_waste, bfs(i, j))

print(food_waste)

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

food_waste: 가장 큰 음식물의 크기

 

음식물들은 근처에 있는 것끼리 뭉쳐 큰 음식물 쓰레기가 된다.

이때 '인접한 것'의 기준은 상하좌우! (대각선은 X)

상하좌우로 이동할 좌표를 리스트에 저장한다.

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

 

사용자에게 좌표 r,c를 입력받아 해당 좌표의 값을 1로 변경한다. (0: 음식물 X, 1: 음식물 O)

이때 주의할 점! arr[r][c] = 1가 아니라 arr[r-1][c-1] = 1로 해야 올바르게 적용된다.

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

 

통로 전체를 돌며, 방문하지 않은 곳이 있다면 bfs를 호출한다.

이때, 매개변수로는 현재 좌표를 넘겨준다.

for i in range(N):
    for j in range(M):
        if not visited[i][j]: # 방문하지 않은 곳
            food_waste = max(food_waste, bfs(i, j))

 

 

✔️ bfs 함수

 

size: 현재 음식물의 크기

 

현재 좌표의 값이 음식물인 경우, deque에 좌표를 추가해준 뒤, 현재 음식물의 크기를 1 증가시킨다.

if arr[x][y] == 1: # 음식물인 경우
        q.append((x,y))
        size += 1

 

deque가 비어있지 않다면, 현재 좌표를 기준으로 상하좌우를 검사한다.

범위를 벗어났거나 이미 방문한 곳이라면 pass~ (continue)

음식물인 경우라면, 마찬가지로 deque에 new 좌표 추가 + 현재 음식물의 크기(size) 1 증가

while q:
        cx, cy = q.popleft()

        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]

            if nx < 0 or nx >= N or ny < 0 or ny >= M or visited[nx][ny]: # 범위를 벗어났거나 이미 방문한 곳인 경우
                continue

            visited[nx][ny] = True

            if arr[nx][ny] == 1: # 음식물인 경우
                size += 1
                q.append((nx, ny))

 

bfs 함수는 현재 음식물의 크기를 반환한다. 음식물이 발견되지 않은 경우라면 0을 반환한다.

return size