BOJ6118 python 그래프 S1

가중치가 1인 그래프에서 가장 먼 정점까지 최단 거리를 구하는 문제

'가중치가 1이라면 bfs로 최단 거리를 구할 수 있다'는 생각이 떠오른다면 맞출 수 있는 문제이다.

from collections import deque

N, M, K = map(int, input().split())
board = [[False for _ in range(M+1)] for _ in range(N+1)]
check = [[False for _ in range(M+1)] for _ in range(N+1)]

for _ in range(K):
	i, j = map(int, input().split())
	board[i][j] = True
	# print(i, j)

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

def bfs(a, b):
	
	Q = deque()
	Q.append((a, b))
	check[a][b] = True

	cnt = 0
	while Q:
		x, y = Q.popleft()
		cnt += 1
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]

			if 1 <= nx <= N and 1 <= ny <= M:
				if board[nx][ny] and not check[nx][ny]:
					Q.append((nx, ny))
					check[nx][ny] = True
	return cnt

mx = 0
for i in range(1, len(board)):
	for j in range(1, len(board[i])):
		if board[i][j] and not check[i][j]:
			mx = max(mx, bfs(i, j))

print(mx)