백준, 사다리 조작(combinations 활용)

백준, 사다리 조작

combinations 활용 풀이

2023.10.13 - [알고리즘] - 백준, 사다리 조작

백트래킹 말고 조합 라이브러리 활용해서 풀어봤다.

❓ 풀이

사다리가 설치가 안된 모든 위치를 list에 저장

이중 1,2,3개의 조합을 뽑아 사다리를 설치

즉, 사다리를 설치할 수 있는 모든 조합에 사다리를 설치 후, 원하는 값 구할 수 있는지 확인

 

📜 제출 코드

C, M, R = map(int, input().split())

regions = [[False for _ in range(C+1)] for _ in range(R)]

for _ in range(M):
    r, c = map(int, input().split())
    regions[r-1][c] = True

# 사다리 정보를 받고 도착지 return 하는 함수
def result(regions):
    res = []
    for h in range(1,C+1):
        for r in range(R):
            if regions[r][h-1]:
                h -= 1
            elif regions[r][h]:
                h += 1
        res.append(h)
    
    return res

wanted_answer = list(e for e in range(1, C+1))

if result(regions) == wanted_answer:
    print(0)
else:
    r_c_list = []
    for r in range(R):
        for c in range(1, C):

            if not regions[r][c]:
                r_c_list.append((r,c))

    answer = -1

    second_flag = False
    for r in range(1,4):
        if second_flag:
            break

        for comb in combinations(r_c_list, r):
            for u_r, u_c in comb:
                if not regions[u_r][u_c] and not regions[u_r][u_c-1] and not regions[u_r][u_c+1]:
                    regions[u_r][u_c] = True

            if result(regions) == wanted_answer:
                second_flag = True
                answer = r
                break
            else:
                for u_r, u_c in comb:
                    regions[u_r][u_c] = False # 설치했던 사다리 없애기
    print(answer)