백준 17472

<다리 만들기 2>

난이도: 골드 1

1. 백준 문제
   17472

2. 코드 알고리즘

• 최소신장트리
  그냥 최소신장트리랑 미로탐색 때려박음
  최소신장트리

• 미로 탐색
  미로 탐색의 코드를 적극적으로 반영했다
  아래코드를 수행하기 위해선 백준 2178을 먼저 이해해야됨.
  2178

• 17472 알고리즘

주어진 행렬을 에지리스트로 변환해야 된다.
이때 백준 2178번 아이디어가 사용된다.

상하좌우 탐색으로 인접 섬을 같은 번호로 일치시킨다.
그리고 변형된 BFS 탐색으로 섬들끼리 다리를 찾는다.

찾은 에지리스트로 최소신장알고리즘에 그대로 수행하면 된다.
단, 에지수 == 노드수 - 1 가 아닌 경우는 최소신장트리가 없는 것이다.

2-1. 슈도코드

17472 슈도코드

#최소신장트리 알고리즘
우선순위 큐 선언
대표노드 저장 리스트

# 행렬
행렬 A 선언하기
n m 입력받기
for i in n:
	n줄동안 list 입력받기

#에지리스트로 변환
#섬 찾기_BFS
dx, dy 선언하기
visitied 선언하기 #2차원 리스트
bfs에서 사용할 큐 선언하기
BFS(행, 열, 분기):
	큐에 시작노드 삽입하기
	visited 리스트에 현재 노드 방문 기록
	while 큐가 빌때까지:
		큐에서 노드 데이터 가져오기
		for 상하좌우 탐색:
			if 유효한 좌표: #지정된 범위내에 있는지
				if 이동할 수 있는 칸이면서 방문하지 않은 노드인지:
				#이동할 수 있는 칸이라는 뜻은 A[해당노드]가 1로 설정돼있는지 확인하기
					visited 리스트에 방문기록
					A리스트에 현재 분기 설정(2번째 분기일 경우 2번째 섬이므로) =>A[][] = 분기
					큐에 데이터 삽입

#가로줄 만큼 bfs 수행하기
for i in 행:
	for j in 열:
		#각 가로줄에서 섬 찾기
		A값이 1인 격자 찾기:
			bfs(행, 열, 분기)
			분기 += 1

# 다리 찾기
에지리스트 선언하기
BFS 반복 #방문리스트 초기화?
방문하지 않은 노드로 가로줄/세로줄 수행 
#방문하지 않은 노드가 dx, 즉 가로방향으로 갈 경우 이후에도 쭉- 가로 연산만 수행하기
다리 거리값 계속 더하기
끝이 다른 섬(A값이 0이 아닌 친구로 만날경우):
	#도착 섬 분기 값 저장하기
	다리 거리값이 2이상인지 확인:
		2이상일경우 (다리 거리값, 출발 섬 번호, 도착 섬 번호) 에지리스트에 저장



#main
for 섬 개수만큼(k): #각 1,2,3,4에 대해 수행하기
	for i N:
		for J:
			if A[][] = 섬번호(k):
				#해당 섬의 격자 찾은 거임
				BFS(i,j,k) #섬번호
	
	

#BFS2
BFS(i, j, k):
	큐 선언
	큐에 대입하기
	while 큐:
		큐 pop하기 #해당 격자 선택하기
		for 4번:
			x= now +dx
			y = now+dy
			while:
				if 범위 내에 있고:
					if A[][] == 0 :
						#dx=-1인 경우만 됨. 이때 계속 dx=-1인 경우로만 진행해야됨
						x += dx, y+= dy #계속 설정한 방향으로만 이동하기
						다리수 += 1
					elif A[][] != k : #자기자신 섬 아닌경우
						#다른 섬에 도달한 거임
						에지리스트에 저장하기 (다리수, k, A[x][y]) #다리수, 출발 섬, 도착 섬
						break
					else:
						#자기 섬의 다른 격자이므로
						break
				else:
					break #끝에 도달했으므로 break하기


#에지리스트 설정됐으므로
#이후로는 최소 신장트리 알고리즘 이용하기
-> 수정필요: 다 연결돼있지 않은 경우를 어떻게 판별?
-> 중복되는 다리수들은 어떻게 영향끼침? (4,2,2), (4,2,2)같은 경우

솔직히 슈도코드 짜면서 당연히 안될거라 생각했다.
너무 길고 너무 단순하고 너무 짜집기 코드다
근데 됐다ㄷㄷ
이왜진?

3. 코드

#17472
#https://www.acmicpc.net/problem/17472

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

#행렬 입력
A=[]
N, M = map(int,input().split())
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)

'''에지리스트로 변환하기'''
#섬찾기
dx = [0,1,0,-1]
dy = [1,0,-1,0]
visited = [[False]*M for _ in range(N)]

def BFS(i, j, depth):
    global check
    check = True
    queue = deque()
    queue.append((i,j))
    visited[i][j] = True
    A[i][j] =depth
    while queue:
        now = queue.popleft()
        for k in range(4):
            x = now[0] + dx[k] #이제부터 x와 y는 이동된 좌표
            y = now[1] + dy[k]
            if x>=0 and y>=0 and x<N and y<M:
                if A[x][y] == 1 and not visited[x][y]:
                    visited[x][y] = True
                    A[x][y]= depth
                    queue.append((x,y)) #dx, dy만큼 이동된 새로운 격자

#가로줄만큼 bfs 수행하기
#섬 번호 부여하기
depth=1
for i in range(N):
    check = False
    for j in range(M):
        if A[i][j] == 1 and not visited[i][j]:
            BFS(i, j, depth)
            if check:
                depth+=1
'''
for i in range(N):
    print(A[i])
#섬 완성
'''


def BFS2(i, j, k):
    queue = deque()
    queue.append((i,j))
    while queue:
        now = queue.popleft()
        for r in range(4):
            distance = 0
            x= now[0]+dx[r]
            y= now[1]+dy[r]
            while True:
                if x>=0 and y>=0 and x<N and y<M:
                    if A[x][y] == 0: #다리가 될 수 있으면
                        x += dx[r]
                        y += dy[r] #설정한 방향으로만 나아가기
                        distance += 1
                    elif A[x][y] != k and distance>1:
                        que.put((distance, k, A[x][y]))
                        break
                    else:
                        #자기 섬의 격자 또는 다리 거리 값이 1일 경우
                        break
                else:
                    break

# 다리 찾기
que = PriorityQueue()
depth -= 1 #depth-1이 섬의 개수
#1다리에서 2,3,4 섬으로 가는 다리수는 3개
for k in range(1, depth+1): #depth-1이 다리수 이므로
    for i in range(N):
        for j in range(M):
            if A[i][j] == k:
                BFS2(i,j,k)

# 다리 완성!

'''에지리스트 완성'''

'''최소신장트리'''
#최소신장트리 알고리즘
parent = [0]*(depth+1) #부모리스트
for i in range(1, depth+1):
    parent[i] = i

def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

def union(a,b):
    parent_a = find(a)
    parent_b = find(b)
    parent[parent_b] = parent_a

result = 0
edge = 1

while que.qsize()>0:
    #depth-1 이 다리 개수
    now_node = que.get()
    if find(now_node[1]) != find(now_node[2]):
        #에지리스트가 중복되는 경우는 if문을 통과 못함
        #그래서 다리수만큼만 반복하면 됨
        union(now_node[1], now_node[2])
        result += now_node[0]
        edge+=1

if edge == depth:
    print(result)
else:
    print(-1)

4. 코드 후기

코드가 길고
중복이 있으며
섬 개수를 작게 제한두지 않았다면 100% 시간초과로 실패했을 것
(백준 검사진이 반례를 적게 둬서 맞았고 실제로는 내 코드 어딘가는 틀렸을 것 같다)

가독성이 좋지 않고 억지로 코드들을 집어넣었더라도
기분이 개째진다