본문 바로가기
Algorithm/DFS&BFS&백트래킹&재귀

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

by HANNI하니 2023. 1. 20.

사용 언어 - Python3

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

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

 

 

정답

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)

❓ 문제 - 백준 스타트와 링크 14889번 - python 풀이법 출처 (https://www.acmicpc.net/problem/14889) 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (

developer-ellen.tistory.com

 

 

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

1️⃣서론

Kyun2da.github.io

  • 깃허브 정답
 

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

코딩테스트 공부. Contribute to yyeongeun/codingtest development by creating an account on GitHub.

github.com

 

'Algorithm > DFS&BFS&백트래킹&재귀' 카테고리의 다른 글

[백준] 25501번 재귀의 귀재  (0) 2023.01.23
[백준] 10872번 팩토리얼  (0) 2023.01.23
[백준] 14888번 연산자 끼워넣기  (0) 2023.01.19
[백준] 2580번 스도쿠  (0) 2023.01.19
[백준] 9663번 N-Queen  (0) 2023.01.19

댓글