[구름톤 챌린지] Day13 : 발전기(2)

입력 및 출력

소스 코드

from collections import deque

n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
visited = [[False for _ in range(n)] for _ in range(n)]
danzi = [0 for _ in range(31)]
dydx = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(n):
	for j in range(n):
		if not visited[i][j]:
			num = a[i][j]
			q = deque([(i, j)])
			visited[i][j] = True
			count = 1
			checked = False
			if count >= k and not checked:
				checked = True
				danzi[num] += 1
			while q:
				y, x = q.popleft()
				for dy, dx in dydx:
					ny, nx = y + dy, x + dx
					if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx] and a[ny][nx] == num:
						count += 1
						visited[ny][nx] = True
						q.append((ny, nx))
						if count >= k and not checked:
							checked = True
							danzi[num] += 1
maxValue = danzi[1]
maxIndex = 1
for i in range(2, 31):
	if danzi[i] >= maxValue:
		maxValue = danzi[i]
		maxIndex = i
print(maxIndex)

문제 풀이

단지 수를 세는 문제이다. 상하좌우로 연결된 같은 숫자끼리 그룹화한 다음, 그 그룹 원소의 수가 K개 이상일 경우 단지라고 판단해야한다.

단계적으로 해결하는 것 같이 적었지만, 윗 줄을 모두 한 번에 처리할 수 있도록 코드를 구성했다.

 

같은 숫자끼리 그룹화 하면서(그래프 탐색 기법 사용) 원소의 개수를 세주고, 그 원소의 개수가 K 이상이 될 경우 단지 값을 1 증가시킨다.

 

같은 숫자끼리 그룹화 하는 방법으로는 전형적인 deque를 이용한 BFS(너비 우선 탐색) 방법을 채택했다.

boolean 변수 checked는 if count >= k 조건의 오점을 보완하기 위해서 사용했다. 만약 count >= k 조건만 사용한다면 그룹의 원소의 개수가 k개, k+1개, k+2개, ... 가 될때 마다 단지 수를 1 증가시키기 때문이다.(실제로 단지 수는 그룹의 원소의 개수가 k+2개든 k개든 1 이다.) 그래서 단지 수를 더하는 연산을 수행했을 때, checked 변수를 True값으로 바꿔주도록 코드를 작성했다.

 

느낀 점

소위 말하는 '스파게티 코드' 형식이 된 것은 아닌가.. 하는 생각이 든다. 왜냐하면 모든 오점이 없이 깔끔한 코드를 작성한 것이 아니라, 이미 작성해놓은 코드에서 발생하는 오류를 하나하나 따로 고쳐서 작성했기 때문이다. 이보다 더 효율적이고 더 깔끔하면서 더 짧은 코드가 반드시 존재할 것이다. 클린 코드를 작성하는 방법을 알면 좋을 것 같다.

그리고 코드를 작성할 때 시간 복잡도와 공간 복잡도를 스스로 정확하게 체크하고 넘어가지 않는 습관도 차차 고쳐야겠다는 생각을 하고있다.