[Python] 구름LEVEL : 개미와 진딧물

머리말

최근 구름LEVEL에서 알고리즘 먼데이 챌린지에 참가하고 있다.

해당 챌린지는 매주 월요일에 4문제를 2시간 안에 푸는 코딩 테스트를 진행하고, 그 다음 주에 해설 강의를 제공하는 챌린지이다.

코린이를 위한 프로그램 같지만,, 생각보다 어렵다는 점 😇

스탬프를 얻으면 소소한 간식도 얻을 수 있으니 추천ㅋㅋ

 

이번 주차의 1번 문제로 개미와 진딧물 문제로 그래프 문제가 나왔다.

 

접근법

처음에는 BFS 문제인 줄 알고, 개미집 위치를 queue에 모두 넣고 bfs 순회하며 거리를 계산했다.

제출하니 시간초과로 통과하지 못했다.

 

문제를 단순하게 생각해보자. 입력 값의 범위가 작다! ➡️ 완전 탐색

개미집과 수액의 거리를 완전탐색하며 Manhattan distance 거리를 계산하고, 그 거리가 m 보다 작다면 정답으로 카운트하였다.

 

코드

n,m=map(int,input().split())
gaemijib=[]
suaek=[]
answer=0
for i in range(n):
	a = list(map(int,input().split()))
	for j in range(n):
		if a[j] == 1:
			gaemijib.append((i,j))
		elif a[j] == 2:
			suaek.append((i,j))

for gx, gy in gaemijib:
	for sx, sy in suaek:
		if abs(gx-sx) + abs(gy-sy) <= m:
			answer += 1
			break
print(answer)