[백준 1743] 음식물 피하기
그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
문제
코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.
이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.
통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.
선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.
입력
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.
좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다.
출력
첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.
예제 입력
3 4 5
3 2
2 2
3 1
2 3
1 1
예제 출력
4
문제 풀이
처음엔 데이터를 입력받고 그래프로 만드는 과정에서 sys 임포트 없이 반복문을 돌려 그래프를 만들었다. 통과는 했지만 시간복잡도에서 효율성이 떨어졌다.
from collections import deque
n,m,k = map(int, input().split())
position = [list(map(int, input().split())) for _ in range(k)]
graph = [[0]*m for _ in range(n)]
result = 0
for i in position:
graph[i[0]-1][i[1]-1] = 1입력받는 순간 그 입력값 좌표의 그래프 노드를 바로바로 변경했더니 훨씬 빨라졌다.
방문여부를 담을 visited 리스트를 따로 만들지 않고 방문한 노드에는 3을 넣었다.
import sys
from collections import deque
n,m,k = map(int, input().split())
graph = [[0]*m for _ in range(n)]
result = 0
for _ in range(k):
r, c = map(int, sys.stdin.readline().split())
graph[r-1][c-1] = 1
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(x,y):
queue = deque()
queue.append((x,y))
cnt = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if nx<0 or ny<0 or nx>=n or ny>=m:
continue
if graph[nx][ny] == 0:
graph[nx][ny] = 3
if graph[nx][ny] == 1:
queue.append((nx,ny))
graph[nx][ny] = 3
cnt += 1
return (1 if cnt==0 else cnt)
for i in range(n):
for j in range(m):
if not graph[i][j] == 3:
k = bfs(i,j)
if k > result:
result = k
print(result)