링크 : https://www.acmicpc.net/problem/1743
1743번: 음식물 피하기
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다
www.acmicpc.net
- 문제
- 소요시간: 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를 선언해서 구해야한다.
'알고리즘(백준) > BFS & DFS' 카테고리의 다른 글
| [알고리즘/BFS & DFS] 6593번 : 상범 빌딩 - python (0) | 2024.02.03 |
|---|---|
| [알고리즘/BFS & DFS] 5014번 : 스타트링크 - python (0) | 2024.02.03 |
| [알고리즘/BFS & DFS] 13913번 : 숨바꼭질 4 - python (0) | 2024.02.03 |
| [알고리즘/BFS & DFS] 13549번 : 숨바꼭질 3 - python (0) | 2024.02.03 |
| [알고리즘/BFS & DFS] 12851번 : 숨바꼭질 2 - python (0) | 2024.02.02 |