[BOJ/백준] 1743. 음식물 피하기 (Python)

🔎 문제

🔗 백준 1743번 음식물 피하기

💡 풀이

일반적인 DFS, BFS와 똑같고 나는 BFS로 풀었다. DFS로 풀었을 때 시간 초과가 발생했던 것 같다.

방문하지 않았던 노드들을 탐색하면서 최댓값을 구해주면 된다.

처음에 방문 배열을 업데이트 해 주지 않아서 메모리 초과가 발생했다. 그리고 난 이문제를 풀면서 가로 세로가 겁나게.. 헷갈렸다. 덕분에 쓸데없이 인덱스 에러와 싸우느라 시간을 많이썼다.

처음에 배열에 음식물을 체크할때 y와 x를 바꾸어 넣어줬는데 이러니까 나머지가 그냥 다 헷갈렸다. 해결방법은 딱히 없는거같고 그냥 그림그리면서 차분히 다시 생각해보았다. 내 머리는 믿으면 안된다 ㅜ

📃 소스코드

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

# n: 세로, m: 가로
n, m, k = map(int, input().split())
matrix = [[0] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]

for _ in range(k):
    x, y = map(int, input().split())
    matrix[x - 1][y - 1] = 1

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
result = -sys.maxsize

def bfs(x, y):
    count = 1
    Q = deque([(x, y)])
    visited[x][y] = True
    
    while Q:
        x, y = Q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if matrix[nx][ny] == 1 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    Q.append((nx, ny))
                    count += 1
    return count
    
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1 and not visited[i][j]:
            result = max(result, bfs(i, j))
            
print(result)

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️