[알고리즘/BFS & DFS] 1743번 : 음식물 피하기 - python

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

1743번: 음식물 피하기

 

---

• 문제
• 소요시간: 15분 6초

---

• 설계하기(접근방법) 

1. 입력받기

행열 크기와

쓰레기 위치를 입력받는다

 

2. 구현하기

다른 문제들과 같다.

입력받는 행열을 탐색하고

bfs 한번을 수행할 때 몇번의 q.apppend()가 이루어지는지 카운트하면

그것이 넓이이다

 

 

3. 출력하기

가장 큰 넓이를 출력한다

 

 

---

• 코드(출력)

from collections import deque


def bfs(x,y):
    q = deque()
    q.append([x,y])
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    visited[x][y] = 1
    count = 1
    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 visited[nx][ny] == 0 and graph[nx][ny] == 1:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append([nx,ny])
                    count += 1
    return count


n , m, trash = map(int,input().split())
visited = [[0 for _ in range(m)] for _ in range(n)]
graph = [[0 for _ in range(m)] for _ in range(n)]

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

area = []
for i in range(n):
    for j in range(m):
        if visited[i][j] == 0 and graph[i][j] == 1:
            a = bfs(i,j)
            area.append(a)
print(max(area))

---

• 얻어갈 부분

1. bfs의 단계 자체를 visited의 기록했는데 그것은 깊이를 나타내는것이기 때문에 넓이를 보장하지 않는다. 따로 count를 선언해서 구해야한다.