[n1743] 음식물 피하기 | python | BFS

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

1743번: 음식물 피하기

---

(처음 든 생각)

BFS로 푸는건가?

DFS..?

일단 BFS로 한 번 해보자! 

---

(풀이)

어마무시하게 시간이 오래 걸렸다..

ㅎ...

마지막 for문을 비효율적으로 돌려서 그런가... ㅠㅠ

현재 위치에 음식물 쓰레기가 있는 경우(1)에만 bfs를 작동시켰다.

 

bfs가 작동되면

그리고 음식물쓰레기가 현재 위치에 있다면 num+=1

없으면 그냥 넘어간다.

현재 위치는 방문처리(-1)가 된다.

 

상하좌우로 체크해서 음식물 쓰레기가 있으면 num+=1

그리고 방문처리

큐에 nx,ny를 넣어준다.

 

 

from collections import deque

r, c, k = map(int, input().split())  # 세로,가로,음식물 쓰레기 개수
array = [[0 for _ in range(c + 1)] for _ in range(r + 1)]
for i in range(k):
    n, m = map(int, input().split())
    array[n][m] = 1

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

answer = 0


def bfs(i, j):
    global answer
    num = 0
    queue = deque()
    queue.append((i, j))

    while queue:
        i, j = queue.popleft()
        if array[i][j] == 1:
            num += 1
        array[i][j]=-1
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if 0 < nx <= r and 0 < ny <= c:
                # 맵 안에 있는 경우
                if array[nx][ny] == 1:
                    num += 1
                    array[nx][ny] = -1  # 방문처리
                    queue.append((nx, ny))
                    continue
    answer = max(answer, num)

for i in range(1, r + 1):
    for j in range(1, c + 1):
        if array[i][j] == 1:
            bfs(i, j)

print(answer)

---