[백준] 14889번: 스타트와 링크 - Python

링크: https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

아이디어

• 그냥 백트래킹으로 2명을 뽑는 경우 2가지를 만들고
• 만들어졌을 때 스타트와 링크의 전력차이를 구하여 최소값과 비교하며 저장하면 될듯?

구현(틀림)

import sys
input=sys.stdin.readline

def back():
    global minv
    if len(tmp) == 2:
        start = li[tmp[0][0]][tmp[0][1]] + li[tmp[0][1]][tmp[0][0]]
        link = li[tmp[1][0]][tmp[1][1]] + li[tmp[1][1]][tmp[1][0]]
        minv = min(minv, abs(start-link))
        print(tmp, start, link)
        return
    for i in range(n):
        for j in range(i, n):
            if i!=j and (i,j) not in tmp:
                tmp.append((i,j))
                back()
                tmp.pop()



n = int(input())

li = [list(map(int, input().split())) for _ in range(n)]

minv = int(1e9)
tmp = []

back()
print(minv)

틀린 원인 분석 

• 위 코드는 스타트팀에 들어간 사람을 링크 팀에도 넣어버린다.
• 방문처리를 통해 중복이 일어나지 않도록 하자

구현(또 틀림)

import sys
input=sys.stdin.readline

def back():
    global minv
    if len(tmp) == 4:
        start = li[tmp[0]][tmp[1]] + li[tmp[1]][tmp[0]]
        link = li[tmp[2]][tmp[3]] + li[tmp[3]][tmp[2]]
        minv = min(minv, abs(start-link))
        print(tmp, li[tmp[0]][tmp[1]], li[tmp[1]][tmp[0]], li[tmp[2]][tmp[3]], li[tmp[3]][tmp[2]], abs(start-link))
        return
    for i in range(n):
        for j in range(i, n):
            if i!=j and i not in tmp and j not in tmp:
                tmp.append(i)
                tmp.append(j)
                back()
                tmp.pop()
                tmp.pop()



n = int(input())

li = [list(map(int, input().split())) for _ in range(n)]

minv = int(1e9)
tmp = []

back()
print(minv)

틀린 원인 분석 2 (하.. 이런 멍청이)

• 문제를 똑바로 읽자 ... 
• 스타트팀과 링크팀에 팀원이 2명이라고 누가 그랬나 팀원은 각 n//2명 이다.... 
• 그럼 n//2명을 뽑고 방문처리를 한자
• 다 뽑았으면 이중 for문을 돌며 둘 다 방문처리가 되어있는 지점과 둘 다 방문처리가 되어있지 않은 지점을 각가 찾아스타트와 링크를 구한다.
• 이후 전력차를 구하여 minv와 비교 후 더 작은걸 minv에 저장.

구현(정답)

import sys
input=sys.stdin.readline

def back(cnt, idx):
    global minv
    if cnt == n//2:
        start = 0
        link = 0
        for i in range(n):
            for j in range(i, n):
                if visit[i] and visit[j]:
                    start += (li[i][j] + li[j][i])
                elif not visit[i] and not visit[j]:
                    link += (li[i][j] + li[j][i])
        minv = min(minv, abs(start - link))
        return
    
    for i in range(idx, n):
        if not visit[i]:
            visit[i] = True
            back(cnt+1,i)
            visit[i] = False



n = int(input())

li = [list(map(int, input().split())) for _ in range(n)]

minv = int(1e9)
visit = [False]*n
back(0, 0)
print(minv)

예스!

마무리

• 문제에서 제시하는 조건을 잘 보자..
• 예제만 보고 문제를 유추해버리는 경향이 있다..
• 그래도 조건을 다시 인지하고 푸니까 한번에 풀리긴 한다.