백준 14889 - 스타트와 링크

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

14889번: 스타트와 링크

 

 

답이 나오긴 했는데 시간초과가 계속 떠서 결국 맞추진 못한 문제이다.

쩝,,

 

정답 코드와 비교해보니 알고리즘은 똑같았는데 함수가 동작할 때 시간을 많이 잡아먹게끔 구현해서 시간초과가 발생했다.

 

알고리즘 흐름은 다음과 같다.

 

1. 스타트와 링크 두 팀으로 나눠야하는데 결국 한 팀만 구하면 다른 팀은 자동으로 구해진다.

=> 0번 팀원을 기준으로(0번 행 기준) 0번 팀원과 같은 팀인 경우 vs 아닌 경우 이렇게 나눴다.

==> 하나의 팀이 구해지면, 해당 팀에 들어가지 않는 팀원들을 구해서 점수를 구했다.

 

2. DFS도 재귀함수의 호출로 이루어지므로 종료조건을 정해야한다.

종료조건은 한 팀의 팀원수가 전체의 1/2일 경우로 했다. 

 

3. 두 팀의 점수차의 최소값은 함수 종료 조건마다 두 팀의 점수차와 m의 최소값으로 m변수를 계속 업데이트했다.

 

사실 알고리즘은 정말 별게 없다. 시간초과가 발목을 잡아서 그렇지..

 

시간초과가 난 코드를 먼저 리뷰해보도록 하겠다.

def DFS(index):
    global m
    total1 = 0
    total2 = 0
    if len(index) == n//2:
        for i in range(n):
            for j in range(n):
                if i in index and j in index:
                    total1 += s[i][j]
                elif i not in index and j not in index:
                    total2 += s[i][j]
        m = min(m, abs(total1 - total2))
        return

    else:
        for i in range(n):
            if i not in index:
                index.append(i)
                DFS(index)
                index.pop()

n = int(input())
s = []
for i in range(n):
    s.append(list(map(int, input().split())))

m = 1e9
DFS([0])
print(m)

굉장히 간단하게? 풀었다.

DFS의 인자로 idex리스트만 넘겼는데 반복문을 돌면서 이미 방문한 인덱스는 패스하고

방문하지 않은 인덱스는 인덱스 리스트에 추가해서 계속 탐색을 했다.

방문한 인덱스 리스트의 크기가 n//2와 같을 경우 종료되게끔 구현했다.

시간초과가 난 이유에 대해 생각해보자면, 

아마 해당 인덱스의 방문 여부를 if i in index 이걸로 했는데 여기서 시간을 많이 잡아먹는 것 같고

팀원이 전체의 1/2이 안될 경우 else로 들어가서 계속 반복문을 돌게끔 되어있는데 계속 처음부터 탐색하는 대참사 발생~ ==> for i in range(n)부분ㅋ

종료 조건에서 in lndex 와 noi in index를 사용했는데 이것도 많이 잡아먹는 것 같다.

이렇게 보니 정말 쩝이네요

 

 

그래서 두 번쨰로 시도한 방법이 in index, not in index를 사용하지 않기 위해서 visited 리스트를 만들어서 해당 인덱스의 방문 여부를 False와 True로 설정한 방법이다.

def DFS(depth, visited):
    global m
    total1 = 0
    total2 = 0
    if depth == n//2:
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    total1 += s[i][j]
                elif not visited[i] and not visited[j]:
                    total2 += s[i][j]
        m = min(m, abs(total1 - total2))
        return

    else:
        for i in range(n):
            if not visited[i]:
                visited[i] = True
                DFS(depth+1, visited)
                visited[i] = False

n = int(input())
s = []
for i in range(n):
    s.append(list(map(int, input().split())))

m = 1e9
visited = [False] * n
visited[0] = True
DFS(1, visited)
print(m)

근데 이것도 시간초과가 났다.

 

풀이 코드랑 비교해보니까 팀원이 전체의 1/2이 되지 않았을 경우 다음 팀원을 탐색하는데, 이 때 range(n)을 사용해서 계속 처음부터 탐색하는 부분에서 차이가 났다.

==>

그래서 idx 변수를 따로 만들어서 다음 팀원 탐색시에 어디서부터 탐색을 시작하면 될지 넘겨주었다.

풀이 코드)

def DFS(depth, visited, idx):
    global m
    start = 0
    link = 0
    if depth == n//2:
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    start += s[i][j]
                elif not visited[i] and not visited[j]:
                    link += s[i][j]
        m = min(m, abs(start - link))
        return

    else:
        for i in range(idx, n):
            if not visited[i]:
                visited[i] = True
                DFS(depth+1, visited, i+1)
                visited[i] = False

n = int(input())
s = []
for i in range(n):
    s.append(list(map(int, input().split())))

m = 1e9
visited = [False] * n
visited[0] = True
DFS(1, visited, 1)
print(m)

 

중간 else 안에 보면

        for i in range(idx, n):
            if not visited[i]:
                visited[i] = True
                DFS(depth+1, visited, i+1)
                visited[i] = False

여기서 idx부터 n-1까지 반복문이 돌아가게 수정했다.

DFS()를 다시 호출할 땐 idx가 현재 방문한 인덱스의 다음 인덱스부터 돌아가게끔

idx에 i+1의  값을 넘겨주었다.

 

시간초과가 나면 반복문을 아예 쓰지 않을 생각만 하고 있었는데

반복문의 반복 크기를 줄여볼 생각도 해봐야겠다..!