[BOJ] 1743번 음식물 피하기 / 사용언어 : 파이썬(python)

※ 문제링크

1743번: 음식물 피하기

해당문제는 탐색과 관련된 문제로 DFS나 BFS를 통해 해결할 수 있는 문제였다. 이번 풀이에서는 BFS를 통해 문제를 해결했는데, 문제해결의 핵심은 쓰레기들의 위치를 기록 및 표기하고, 인접해있는 쓰레기들의 수의 최댓값을 출력하는 것이었다. 문제를 해결하면서 방문여부는 따로 배열을 만들지 않고, 쓰레기들의 위치를 기록한 기본테이블을 약간 변형하였으며, 해당 문제는 최단거리를 찾는 것이 아니라 인접한 쓰레기들의 숫자를 구하는 것이므로 한번 탐색시마다 cnt에 +1을 해주어 문제를 해결하였다. 자세한 문제풀이방법과 코드는 아래와 같다.

1. 입력받은 값들 각각의 변수에 할당하고, 해당 변수들을 바탕으로 NxM크기의 배열을 생성한다.

2. 반복문을 통해 입력값들을 리스트에 저장하고, 해당 배열 좌표를 1로 변경한다.

3. 상하좌우를 탐색할 수 있는 BFS함수를 작성하고, 한번 탐색한 위치값은 2로 변경하여 차후에 탐색을 할때에 재탐색이 이루어지지 않도록 작성한다.(방문여부를 한번에 기록)

4. 반복문을 활용하여 2번 과정에서 저장해놓은 좌표들을 BFS함수에 대입하여 cnt값을 구하고 ans값보다 cnt의 값이 크면 ans를 대체한다.(+메모리 및 시간 절감을 위해 sys를 사용했습니다.)

 

from collections import deque
import sys

N, M, K = map(int, input().split()) # N: 세로길이 / M: 가로길이 / K: 음식물 개수
# input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
locs = []
field = [[0 for _ in range(M+1)] for _ in range(N+1)]
for _ in range(K):
    y, x = map(int, input().split())
    locs.append([x, y])
    field[y][x] = 1
 
def bfs(x, y):
    queue = deque()
    queue.append([x, y])
    field[y][x] = 2

    cnt2 = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M+1 and 0 <= ny < N+1 and field[ny][nx] == 1:
                field[ny][nx] = 2
                queue.append([nx, ny])
                cnt2 += 1
            
    return cnt2


ans = 0
for loc in locs:
    nx, ny = loc
    cnt3 = bfs(nx, ny)
    if ans < cnt3:
        ans = cnt3
print(ans)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.