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

사용 언어 - Python3

14889번: 스타트와 링크 (실버2, DFS 백트래킹 문제)

문제 ★백트래킹 문제, 삼성 SW 역량 테스트 기출 문제 ★

14889번: 스타트와 링크

 

 

정답

DFS 백트래킹 재귀함수 조합 문제 !!

다른 분들 답중에 가장 좋다고 생각하는 풀이법 2가지로 공부했습니다. 맨 아래에 링크를 올립니다!

 

1.  방문 여부에 따라 팀 지정하는 방법

1팀은 2팀이 방문하지 않은 곳, 2팀은 1팀이 방문하지 않은 곳으로 생각한다.

visited[i]를 순차적으로 방문해서 visited를 True로 해준다.

n명의 절반을 방문한 경우 = 팀원이 모두 배정된 경우 = 특정 팀만 visited = True인 경우, 

visited가 False인 경우는 1팀능력치에 더해주고, True인 경우는 2팀능력치에 더해준다.

두 능력치의 min 최소값을 구하고 dfs를 마친다.

dfs를 마치면 방문한 곳을 다시 visited = False로 만들어주어 리셋해준다.

# 정답1
def dfs(depth,idx):
    global min_diff
    
    if depth == n//2:
        power1, power2 = 0,0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    power1 += graph[i][j]
                elif not visited[i] and not visited[j]:
                    power2 += graph[i][j]
        min_diff = min(min_diff,abs(power1-power2))
        return
    
    for i in range(idx,n):
        if not visited[i]:
            visited[i] = True
            dfs(depth+1,i+1)
            visited[i] = False
            
n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
visited = [False for _ in range(n)]

min_diff = int(1e9)
dfs(0,0)
print(min_diff)

 

2. 각각의 능력치 인덱싱

start, link 빈 리스트를 선언하여 멤버를 한 명씩 넣어준다.

start팀을 기준으로 start에 i가 없을 때 i를 append하면서 dfs을 시행한다.

만약 start팀에 i가 이미 들어가 있어서 start팀에 못들어갔다면 link팀안에 append해준다.

예) start = [1 2] , link = [3 4]

start팀능력치를 구하려면 graph에 (1,2)에 있는 능력과 (2,1)에 있는 능력을 더해줘야한다.

startSum += grpah[start[1]][start[2]] + graph[start[2]][start[1]]

이때 팀 수에 따라 인덱싱이 달라지는 점을 for문 범위를 통해 해결한다. range(0, n//2-1), range(i+1,n//2)

두 능력치의 min 최소값을 구하고 dfs를 마친다.

dfs를 마치면 방문한 곳을 start.pop()으로 start팀에 속한 맨 마지막 팀원부터 없애주면서 팀원을 변경해준다.

# 정답2
def dfs(index):
    global min_diff
    
    if index == n // 2:
        startSum = 0
        linkSum = 0
        for i in range(0,n):
            if i not in start:
                link.append(i)
        for i in range(0, n // 2 - 1):
            for j in range(i+1, n // 2):
                startSum += graph[start[i]][start[j]] + graph[start[j]][start[i]]
                linkSum += graph[link[i]][link[j]] + graph[link[j]][link[i]]

        min_diff = min(min_diff,abs(linkSum-startSum))
        link.clear()
        return

    for i in range(n):
        if i in start: continue
        if len(start)>0 and start[len(start)-1]> i : continue
        start.append(i)
        dfs(index + 1)
        start.pop()


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

min_diff = float('Inf')
dfs(0)
print(min_diff)

 

 

개인적으로 2번의 방법으로 접근했어서 이해가 훨씬 쉬웠으나, 1번이 훨씬 코드 간편화했기 때문에 1번의 방법으로 공부했습니다.

두 방법 모두 메모리와 코드길이는 같으나, 방법1이 방법2보다 시간이 많이 걸린 것을 확인할 수 있었습니다.

(위) 방법1, (아래) 방법2

 

---

레퍼런스

• 정답1, 정답2 참고

 

BOJ - 스타트와 링크 14889번 (python)

 

[백준/Python] 14889 스타트와 링크 - Kyun2da Blog

• 깃허브 정답

GitHub - yyeongeun/codingtest: 코딩테스트 공부