◾ 음식물 피하기 : 백준 1743번
문제
코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.
이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.
통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.
선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.
입력
- 통로의 세로 길이 n, 가로 길이 m, 음식물 쓰레기의 수 k
- k개의 음식물 좌표 (r, c)
- 음식물은 상, 하, 좌, 우 중 하나의 방향으로 붙어있는 경우 커진다.
출력
- 제일 큰 음식물의 크기
입출력 예
| 입력 | 출력 |
|---|---|
| 3 4 5 3 2 2 2 3 1 2 3 1 1 | 4 |
◾ 풀이
1. 해설
- 각 정점에서 연결된 정점의 수를 구하면된다.
DFS,BFS등을 사용하여 해결할 수 있다.BFS(너비 우선 탐색)을 이용해 연결된 정점들의 수를 확인하였다.- 시작 정점부터 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 확인한다.
- 정점들이 연결되어있지 않을 수 있기 때문에 각 정점에서 확인이 필요하다
- 방문한 정점을 모아둘 변수가 필요하다
- 큐, 덱 등을 활용한다.
2. 프로그램
n,m,k,음식물 좌표입력- 각 좌표를 시작 정점으로
BFS실행- 연결된 정점의 수를 구하여
max_size와 비교 - 각 좌표에 방문할 때마다
visited에 추가 visited에 포함된 좌표일 경우 다음 정점 탐색
- 연결된 정점의 수를 구하여
# 코드
from collections import deque
n, m, k = map(int, input().split()) # 세로 길이, 가로 길이, 음식물의 수
# 음식물의 좌표
points = [tuple(map(int, input().split())) for _ in range(k)]
d = [(1, 0), (-1, 0), (0, -1), (0, 1)] # 이동 좌표
visited = [] # 방문 정점 저장 리스트
# 결과값 초기화
# 최대값을 구하는 것이므로 초기값 0으로 설정
max_size = 0
# 모든 정점을 시작 정점으로 BFS 실행
for r, c in points:
# deque을 이용해 시작 정점 추가
edges = deque([(r, c)])
# 현재 정점에서 연결된 정점의 수
this_size = 0
while edges:
# FIFO 동작을 위해 popleft() 사용
p = edges.popleft()
# 방문한 정점인지 검사
if p in visited:
continue
# 처음 방문한 경우 사이즈 +1
# visited 추가
this_size += 1
visited.append(p)
# 현재 정점에서 가능한 위치 확인
for d_r, d_c in d:
next_r, next_c = p[0]+d_r, p[1]+d_c
# points에 속하면서 visited에 속하지않는 경우 추가
if (next_r, next_c) in points and (next_r, next_c) not in visited:
edges.append((next_r, next_c))
# max_size와 this_size 중 최대값 선택
max_size = max(max_size, this_size)
print(max_size)
후라이드 치킨