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

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

 

아이디어

• 전염되어있는 크기를 구하는거니 bfs를 쓰자
• N, M 최대값이 각 100 밖에 안돼서 NxM 전체 탐색해도 시간복잡도 그리 안클거 같음
• NxM 크기의 배열을 각 요소를 0으로 선언해주고 r,c 위치를 다 1로 표시해준다. -> li
• 방문 확인용 배열도 NxM 크기의 각 요소 0인 배열 선언
• li 리스트를 돌며 1인 (쓰레기위치)를 찾으면 방문했던 위치인지 판단.
• 방문하지 않은 위치라면 bfs 함수 호출
  • size를 1부터 시작해서(자기자신) 주변 탐색을 진행
  • 쓰래기 발견시 size+1하는 형식으로 진행
  • bfs 함수는 size 값을 반환
• result는 초기값 0 을 가지고 bfs 함수 호출 시마다 큰 값을 result에 대입해줌
• li 탐색이 모두 완료하면 result 값 반환

구현

import sys
from collections import deque
input = sys.stdin.readline

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

li = [[0]*M for x in range(N)]
visit = [[0]*M for x in range(N)]
mv = [(-1, 0), (0, 1), (1, 0), (0, -1)]

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

def bfs(i, j):
    size = 1
    q = deque()
    q.append((i, j))
    while q:
        y, x = q.popleft()
        for m in mv:
            ny = y + m[0]
            nx = x + m[1]
            if 0<=ny<N and 0<=nx<M:
                if li[ny][nx] == 1 and visit[ny][nx] == 0:
                    q.append((ny, nx))
                    visit[ny][nx] = 1
                    size+=1
    return size

result = 0
for i in range(N):
    for j in range(M):
        if visit[i][j] == 0 and li[i][j] == 1:
            visit[i][j] = 1
            result = max(bfs(i, j), result)

print(result)

 

마무리

그냥 생각나는대로 줄줄 풀었는데 한번에 맞춰서 기분이 좋았다.

기본적인 bfs 문제 얍얍