백준 1414

<불우이웃돕기>

난이도 : 골드 3

1. 백준 문제
   1414

2. 코드 알고리즘

• 최소신장트리
  MST가 최소신장트리였구나
  최소신장트리

• 1414 알고리즘

가장 중요한 아이디어✨
최대랜선길이 == 전체 - 최소 랜선 길이 이다.
왜냐하면 다솜이가 쓸 최소 랜선 길이를 제외한 이외의 랜선은 모두 기부해야되기 때문이다.

2-1. 슈도코드

1414 슈도코드

컴퓨터 개수 N 입력

A #행렬 입력받기

for i in range(N):
	A에 저장

#에지리스트로 변환
#1. 문자를 숫자로 변환하기 (0은 예외 사항)
#아스키 A=65 , A=27
##대문자는 -38 연산 필요 (아스키 범위 65~90)
#아스키 a=97 , a=1 
## 소문자는 -96 연산 필요(아스키 범위 97 ~122)

sum = 0
for i in N:
	for j in N:
		temp = ord("A[i][j]")#ord() 문자->아스키코드
		if temp == 0:
			0으로 그대로 저장
		elif 65~90일경우:
			-38연산 수행하기 
		elif 97~122에선
			-96연산 수행하기
		#다변환한 이후이므로 전체 랜선 길이에 합하기
		sum에 합하기

#에지리스트 구하기
priority queue 선언하기
for i:
	for j:
		자기자신 제외하기
		que에 삽입하기

#최소신장트리 알고리즘 그대로 수행~!
def find 함수
def union 함수

while que 빌때까지 수행:
	최소신장트리 알고리즘	# 사용된 edge 개수 세리기 

사용된 edge 개수가 (노드-1)개일 경우:
	#최소신장트리가 맞으므로 
	print(sum - 최단경로값)
최소 신장트리가 아닐경우:
	-1 출력하기

3. 코드

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

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

N = int(input())
# 문자 행렬 입력받기
A =[]
for i in range(N):
    a= list(input())
    A.append(a[:-1])

#에지리스트로 변환하기
##문자를 숫자로 변환하기
sum = 0
for i in range(N):
    for j in range(N):
        temp = ord(A[i][j])
        if temp == 48: #"0"의 아스키코드 값은 48
            A[i][j] = 0 #int형으로 바꿔주기
        elif 64 < temp < 91:
            A[i][j] = temp - 38
        elif 96 < temp < 123:
            A[i][j] = temp - 96
        sum += A[i][j]

#에지리스트 구하기
que = PriorityQueue()
for i in range(N):
    for j in range(N):
        ##행렬 인덱스가 0부터 시작된다는 거 주의!!
        ##에지리스트에는 인덱스 값이 아닌 노드번호값으로 입력하기
        if j==i: #1번째의 1번째, 2번째의 2번째 ... 는 자기자신
            continue
        elif A[i][j] == 0:
            continue
            #0인경우는 무시하기, 연결안됐음을 의미
        else:
            que.put((A[i][j], i+1, j+1)) #가중치, 출발 노드번호, 도착 노드번호
            #인덱스 + 1 해서 노드번호로 변환하기

#최소신장트리 알고리즘
parent = [0]*(N+1)
for i in range(1, N+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 #b의 부모노드의 부모를 - a의 부모노드로 설정하기

min_tree = 0
edge = 0
#최소신장트리
while que.qsize()>0:
    now = que.get()
    if find(now[1]) != find(now[2]):
        union(now[1], now[2])
        min_tree += now[0]
        edge += 1

if edge == (N-1):
    #최소신장트리가 맞는 경우
    print(sum - min_tree)
else:
    print(-1)

4. 코드 후기

최대 길이라길래 놀람...
잉 최소신장트리 아니였음?
근데 최대로 만들려면 자신이 쓰는 랜선은 최소로 만들어야 되는 거였음
요것만 파악하고 아스키코드만 사용할 줄 알면 기존 최소신장트리 알고리즘이랑 동일!