[코드트리 챌린지] 5주차 - Backtracking

정체중...

아무래도 일주일에 한 문제씩만 풀고 있다보니

당연히 실력 향상은 크게 되지는 않았다.

이번에는 4문제밖에 풀지 못했는데 생각보다 점수가 높게 나와서 의외였다.

DFS에 대한 학습이 더 필요하다고 나왔다.

앞으로 계속해서 Backtracking, DFS 문제들을 풀어나가면서 완벽하게 만들어야겠다.

 

사다리 타기 

문제 링크: https://www.codetree.ai/missions/2/problems/ladder-game?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

3시간 넘게 고민을 하다가 해설을 참고해서 아이디어를 얻은 후 나만의 방식으로 다시 코드를 작성했다.

아래는 본인이 작성한 테스트케이스를 통과한 정답 코드이다.

n, m = tuple(map(int, input().split()))
lines = list()
for _ in range(m):
    a, b = tuple(map(int, input().split()))
    lines.append((b, a))
lines.sort()


def go(person, lines):
    '''한 사람의 결과(위치)를 반환'''
    global n
    cur_b, cur_j = 1, person
    while (True):
        found = False
        for line in lines:
            if line[0] >= cur_b and (line[1] == cur_j or line[1] == cur_j-1):
                found = True
                cur_b = line[0] + 1
                if line[1] == cur_j:
                    cur_j += 1
                else:
                    cur_j -= 1
                break
        if not found:
            break
    return cur_j


def ghostLeg(lines):
    '''게임의 결과를 반환'''
    global n
    global m
    result = [-1 for _ in range(n)]
    for person in range(1, n+1):
        pos = go(person, lines)
        result[pos-1] = person
    return result


def lineCmb(i, cmb):
    '''가능한 가로줄 조합들을 모두 찾아준다.'''
    global cmbs
    if i == m:
        cmbs.append(cmb)
        return
    cmb.append(lines[i])
    lineCmb(i+1, cmb[:])
    cmb.pop()
    lineCmb(i+1, cmb[:])


init_res = ghostLeg(lines)
min_m = m  # 최소 가로줄 수


cmbs = list()
lineCmb(0, [])

for cmb in cmbs:
    if len(cmb) < min_m and init_res == ghostLeg(cmb):
        min_m = len(cmb)

print(min_m)