[멀티잇 코딩테스트 러닝클래스] 그래프(Graph) : 뭉친 K, 모래섬 - 파이썬(Python)

뭉친 K

 

 

 

 

 

 

N*N 크기의 배열 M에서 M[x-1][y-1]과 같은 값들을 찾고 해당 값들이 서로 얼마나 연결되어있는지 판단하여 그 중 가장 길게 연결된 경우를 찾아내는 문제입니다.

 

우선 탐색을 위해 N*N 크기의 Visit과 dx,dy 배열을 준비합니다. Visit은 탐색하지 않은 칸은 0, 이미 탐색한 칸은 1로 표시함으로써 중복 탐색을 막아줄 것입니다. 이후 2차원 배열 M에 주어진 원소들을 추가합니다.

 

이제 탐색을 시작해보겠습니다. 탐색은 Visit[i][j] == 0이고 M[i][j] == K일 때만 실시합니다. deque Q에 [i,j]를 추가해놓은 상태에서 Q가 빌 때까지 상하좌우로 K값을 가진 인덱스가 있는지 탐색합니다. 이때 K값을 가진 인덱스를 발견할 때마다 cnt를 추가시킵니다.

 

탐색이 끝나면 ans = max(ans, cnt) 즉, 뭉친 구간의 최댓값을 저장해주면 되겠습니다.

 

 

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

N = int(input())
x,y = map(int,input().split())
M = []
Visit = [[0 for i in range(N)] for j in range(N)]
ans = 0

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

for i in range(N) :
	M.append(list(map(int,input().split())))
	
K = M[x-1][y-1]

for i in range(N) :
	for j in range(N) :
		if Visit[i][j] or M[i][j] != K :
			continue
		Q = deque()
		Q.append([i,j])
		Visit[i][j] = 1
		cnt = 0
		
		while Q :
			cy,cx = Q.popleft()
			cnt += 1
			for k in range(4) :
				nx = cx + dx[k]
				ny = cy + dy[k]
				if nx < 0 or ny < 0 or nx >= N or ny >= N :
					continue
				if M[ny][nx] != K or Visit[ny][nx] == 1 :
					continue
				Q.append([ny,nx])
				Visit[ny][nx] = 1
		ans = max(ans,cnt)

print(ans)

 

---

 

모래섬

 

 

 

 

 

 

 

 

앞선 문제와 똑같이 dx와 dy를 준비하고 2차원 배열 S에 주어진 원소들을 저장합니다.

 

이후 while문을 통해 어떤 칸의 값이 0이면 해당 칸의 상하좌우를 0으로 만들고 1이 뭉쳐있는 그룹을 탐색하여 그룹의 개수 즉, 섬의 개수가 2 이상이면 반복을 멈추겠습니다. 섬의 개수가 2 이상이 아니어도 S가 모두 0으로 채워져있다면 역시 반복을 멈춥니다.

 

[while 문]

첫번째로 S의 원소가 0인 경우 zero_arr에 해당 인덱스를 저장합니다. 

 

두번째로 zero_arr에서 인덱스(zy,zx)를 하나씩 꺼내, 해당 인덱스의 상하좌우 인덱스가 아직 방문한 적이 없고 값이 1이라면 0으로 교체해줍니다.

 

마지막으로 변경된 S를 탐색하여 [뭉친 K] 문제 알고리즘과 똑같이 1로 뭉쳐있는 그룹을 탐색하고, 그 그룹의 개수를 세면 됩니다.

 

 

from collections import deque
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
S = []
dx = [0,0,-1,1]
dy = [-1,1,0,0]
minute = 0

for i in range(N) :
	S.append(list(map(int,input().split())))

while True : 
	zero_arr = []
	zeroV = [[0 for _ in range(M)] for _ in range(N)]
	oneV = [[0 for _ in range(M)] for _ in range(N)]
	island = 0
	minute += 1
	
	for i in range(N) :
		for j in range(M) :
			if S[i][j] == 0:
				zero_arr.append([i,j])	
			
	for zy,zx in zero_arr :
		zeroV[zy][zx] = 1
		for b in range(4) :
			ny = zy + dy[b]
			nx = zx + dx[b]
			if ny < 0 or nx < 0 or ny >= N or nx >= M :
				continue
			if zeroV[ny][nx] or S[ny][nx] == 0 :
				continue
			zeroV[ny][nx] = 1
			S[ny][nx] = 0
	
	for a in range(N) :
		for b in range(M) :
			oneQ = deque()
			if oneV[a][b] or S[a][b] == 0 :
				continue
			oneQ.append([a,b])
			oneV[a][b] = 1

			while oneQ :
				oy,ox = oneQ.popleft()
				for b in range(4) :
					ny = oy + dy[b]
					nx = ox + dx[b]
					if ny < 0 or nx < 0 or ny >= N or nx >= M :
						continue
					if oneV[ny][nx] or S[ny][nx] == 0 :
						continue
					oneV[ny][nx] = 1
					oneQ.append([ny,nx])
			island += 1
	
	cnt = 1
	for sand in S :
		if 1 in sand :
			cnt = 0
			break
				
	if cnt == 1 :
		minute = -1
		break
	elif island > 1 :
		break
	
print(minute)