[python] 뭉친 K

문제

N × N 크기의 2차원 배열 M이 있다. M의 i번째 줄, j번째 칸을 M[i][j] 라고 하며, 한 칸의 크기는 1이다. 배열의 각 칸에는 0부터 9사이의 숫자가 하나씩 적혀 있다. 이 숫자를 해당 칸의 값이라고 한다.

 

배열 M에는 뭉친 그룹이 있다. 뭉친 그룹이란 상하좌우로 인접한 칸으로 연결되어 있으면서, 모든 칸들이 같은 값을 가지는 칸들의 집합을 의미한다. 뭉친 그룹의 크기는 그 그룹에 속한 칸의 개수와 같다.

 

M[x][y] 칸의 값이 K일 때, 값이 K인 칸으로 이루어진 뭉친 그룹 중 가장 큰 뭉친 그룹의 크기를 출력하시오.

 

 

입력

첫째 줄에 M의 크기 N이 주어진다.

둘째 줄에 x, y가 공백을 두고 주어진다.

다음 N개의 줄에는 M의 상태가 주어진다. i번째 줄에는 M[i][1], ..., M[i][N] 이 공백을 두고 주어진다.

• 1 ≤ N ≤ 500
• 1 ≤ x, y ≤ N
• 0 ≤ M[i][j] ≤ 9
• 입력에서 주어지는 모든 수는 정수이다.

 

 

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
x, y = map(int, input().split())
x, y = x-1, y-1
m = []
v = [[0]*n for _ in range(n)]
for _ in range(n):
	m.append(list(map(int, input().split())))
	
k = m[x][y]

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


result = 0
for i in range(n):
	for j in range(n):
		if v[i][j] or m[i][j] != k:
			continue
		q = deque()
		count = 0
		v[i][j] = 1
		q.append([i, j])
		
		while q:
			cx, cy = q.popleft()
			count += 1
			for z in range(4):
				nx, ny = cx+dx[z], cy+dy[z]
				if nx < 0 or ny < 0 or nx >= n or ny >= n:
					continue
				if v[nx][ny] or m[nx][ny] != k:
					continue
				v[nx][ny] = 1
				q.append([nx, ny])
		result = max(result, count)
print(result)

모든 칸을 순회하면서 해당 칸의 정보를 deque 에 담고 그 주변으로 상하좌우를 판별해서 같은 값이면 그 칸도 deque 에 담고 아니면 넘기는 식으로 풀이하면 해결된다.

지난번 폭탄 구현 문제를 응용하면 될 것 같았는데, 아직 익숙치 않아서 해당 칸의 상하좌우 값을 어떻게 관리하고 사용해야하나 고민을 많이 했던 문제이다.

 

 

※출처

https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-python-6월반