백준, 사다리 조작

백준, 사다리 조작

 

❓문제

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

15684번: 사다리 조작

 

✅ 분류

accepted
 

❓ 풀이

사다리를 1개 설치할 경우, 모든 경우 탐색
사다리를 2개 설치할 경우, 모든 경우 탐색
사다리를 3개 설치할 경우, 모든 경우 탐색
만약, 사다리 3개 설치하고도 원하는 결과를 얻을 수 없는 경우 -1 return
 
현재 위치에서 사다리 설치가능하면 설치
원하는 값 얻을 수 없으면 설치를 취소하고 설치 가능한 다음 위치를 탐색해야 한다. 즉, 백트래킹을 이용하면 되는 문제!
 
이 문제는 사다리와 현재 이동 정보를 2차원 배열로 표현하는 방법이 아주 다양하다.
 

🪴 사다리 배열

 
초기 사다리 배열

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

나의 현재 위치가 오른쪽, 나의 왼쪽 위치가 서쪽 방향!
 
추후 사다리 배열

# C, H, R = 2, 0, 3
C, H, R = map(int, input().split())

regions = [[0 for _ in range(C*2-1)] for _ in range(R)]

# 세로 사다리 설치
for r in range(R):
    for c in range(C*2-1):
        if c % 2 == 0:
            regions[r][c] = 1 # h

# 가로 사다리 설치
for _ in range(H):
    h_r, h_c = map(int, input().split())
    regions[h_r-1][h_c*2-1] = 1 # h

# regions =[[1, 0, 1], [1, 0, 1], [1, 0, 1]]

양 옆으로 살펴보기 좋고 직관적이도록 column 배열을 2*C+1로 늘림.
사실 어떤 식으로 하든 원하는 값을 얻을 수 있는지 여부만 판별하면 되서 크게 상관없다!
 

🪴 시간복잡도 개선

1번 사다리 도달 위치, 2번 사다리 도달 위치 다 확인해서 배열 형태로 변환

# 사다리 정보를 받고 도착지 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

하지만, 이렇게 되면 불필요한 연산을 더 하는 것이므로 1번 사다리가 1번에 도달하지 않으면 바로 False를 return 하는 함수로 고쳐줬다.
 

# 시작 위치와 도착 위치가 동일한지 체크
# 한번 탐색후 동일하지 않으면 바로 return
def check(array):
    answer = True
    for h in range(0, (C*2-1), 2):
        tmp = h
        for r in range(R):
            if 0<= h+1 <(C*2-1) and array[r][h+1] == 1:
                h += 2
                continue
            elif 0<= h-1 <(C*2-1) and array[r][h-1] == 1:
                h -= 2
                continue
        if tmp != h:
            answer = False
            return answer
    return answer

---

📜 최종 코드

# 사다리는 원래 값은 C*2-1
# H = C/2+1

# C, H, R = 2, 0, 3
C, H, R = map(int, input().split())

regions = [[0 for _ in range(C*2-1)] for _ in range(R)]

# 세로 사다리 설치
for r in range(R):
    for c in range(C*2-1):
        if c % 2 == 0:
            regions[r][c] = 1 # h

# 가로 사다리 설치
for _ in range(H):
    h_r, h_c = map(int, input().split())
    regions[h_r-1][h_c*2-1] = 1 # h

# regions =[[1, 0, 1], [1, 0, 1], [1, 0, 1]]


# 시작 위치와 도착 위치가 동일한지 체크
# 한번 탐색후 동일하지 않으면 바로 return
def check(array):
    answer = True
    for h in range(0, (C*2-1), 2):
        tmp = h
        for r in range(R):
            if 0<= h+1 <(C*2-1) and array[r][h+1] == 1:
                h += 2
                continue
            elif 0<= h-1 <(C*2-1) and array[r][h-1] == 1:
                h -= 2
                continue
        if tmp != h:
            answer = False
            return answer
    return answer
        

# 탐색하기
flag = False # 불필요한 재귀호출 방지
def dfs(r, c, cnt, max):
    global answer, C, flag, regions
    if flag:
        return
    if cnt == max:
        if check(regions):
            flag = True
            answer = cnt
            return
        return
    if c == 2*C-1:
        dfs(r+1, 1, cnt, max)
        return
    if r == R:
        return

    # 사다리 설치할 수 없는 경우
    if regions[r][c] == 1 or (0<=c-2<C*2-1 and regions[r][c-2] == 1) or (0<=c+2<C*2-1 and regions[r][c+2] == 1):
        dfs(r, c+2, cnt, max)

    # 사다리 설치할 수 있는 경우
    else:
        regions[r][c] = 1
        dfs(r, c+2, cnt+1, max)

        # check시 False로 return 되면 다시 r,c 예전 위치로 돌아옴. 
        regions[r][c] = 0 # 사다리 제거
        dfs(r, c+2, cnt, max) # 다음 위치에서 탐색 시작

# 추가할 수 있는 최대 사다리는 3개
# 만약 3개 이상 사다리를 추가해야 하면 더 이상 탐색 하지 말고 -1 출력
answer = -1
for i in range(4):
    # 현재 위치 r,c 와 설치한 사다리 갯수 cnt, 설치할 수 있는 최대 사다리 갯수 max
    dfs(0, 1, 0, i)

print(answer)

---

❓ 다른 풀이

2023.10.13 - [알고리즘] - 백준, 사다리 조작(combinations 활용)