백준(15684 사다리 조작)

02 Jul 2020

문제

입력

---

문제 해설

아이펜슬을 어디다가 잠깐동안 잃어버린 관계로,,,, 노트 필기를 조금 넣도록,,,
일단! 이 문제의 핵심은 좌표와 2차배열을 한꺼번에 생각해서 좌표가 헷갈리지 않게 생각해야 되는 것이다. 다음 그림을 한번 봐보자. —–

문제 그림

문제 해설(이어서)

첫번째 그림을 보면 파란색 글씨는 배열에서의 인덱스를 가르키고, 빨간색 글씨는 사다리 타기 할 때의 점의 좌표의 느낌으로 생각하면 되겠다. 자, 그러면 만약에 다리가 설치되있고, 또 앞으로 설치를 할 때는 어떤식으로 표현을 해야할 까? 두번째 그림을 한번 봐보자. 실선으로 진하게 그려진 부분이 다리가 연결되었다는 뜻이다. (0,0) 좌표를 큐에 넣어서 표현을 해도 되지만, 시간을 줄이기 위해 칠해진 부분을 네모의 아랫변으로 보고 왼쪽위 꼭지점이 1이면 다리가 있다는 뜻이 되겠다. 한마디로 말하자면, flag를 담고 있는 map_list가 있다면 map_list[0][0] 이 1이라는 뜻이다. 이러한 자료구조로 백트래킹과 재귀를 이용해서 풀어주면 되겠다!

N, M, H = list(map(int, input().split()))

map_list = [[0] * (N-1) for _ in range(H)]
# bridge_list = []

total_move = 999999999

#세팅되어 있는 맵 입력하기
for _ in range(M):
    a, b = list(map(int, input().split()))
    map_list[a-1][b-1] = 1

#1번부터 시작해서 1번에 1번, 2번에 2번,,, 이 맞나 확인하는 메소드
def go():
    for i in range(N):
        x, y = 0, i #출발 좌표 저장
        orig_y = y #나중에 맞나 비교를 위해 원래 좌표 저장
        while(True):
            #down
            x, y = x+1, y
            if x == H+1:
                break
            #check left
            if x-1 >= 0 and y-1 >= 0 and map_list[x-1][y-1] == 1:
                x, y =  x, y-1
                continue
            #check right
            if x-1 >= 0 and y < N-1 and map_list[x-1][y] == 1:
                x, y = x, y+1
                continue
        #도착했는데 안 같다면 
        if orig_y != y:
            return False
    return True

#추가하는 사다리 갯수별로 함수를 돌릴 것이다.
def solution(cnt, start, limit):
    global total_move
    #써야될 사다리 갯수 다 썼을 때
    if cnt == limit:
        #사다리 타봤는데 1번째에 1번이 안나온다면
        if go() == False:
            return False
        #사다리 탔는데 잘 된다면
        else:
            #최솟값만 골라내기 위해
            if total_move > limit:
                total_move = limit
            return True
    
    #그전에 다리를 놓으면서 재귀 들어갔던 행부터 시작
    for i in range(start, H):
        #열의 마지막까지 돌면서
        for j in range(N-1):
            #다리가 이미 놓아져있다면
            if map_list[i][j] == 1:
                continue
            #다리가 안 놓아져있는데
            if map_list[i][j] == 0:
                #그 왼쪽에 다리가 놓아져있어
                if j-1 >= 0 and map_list[i][j-1] == 1:
                    continue
                #그 오른쪽에 다리가 놓아져있어
                if j+1 <= N-2 and map_list[i][j+1] == 1:
                    continue
            #나의 맵에다가 1을 넣어주고(다리가 놓여져있다)
            map_list[i][j] = 1
            #다리를 마지막으로 놨던 행부터 다시 시작
            if solution(cnt+1, i, limit):
                return True
            #백트래킹의 방법
            map_list[i][j] = 0

#다리 0개부터 돌려보자
for i  in range(4):
    flag = solution(0, 0, i)
    if flag:
        break
    
if total_move == 999999999:
    print("-1")
else:
    print(total_move)

dfs/bfs 문제들을 너무 오랜만에 풀었는데 감을 다시 잡아야겠다,,, 내인생,,,화이팅… , 아니 이거 근데 그냥 브루트포스로 다 뒤지는 문제자나,,,, 어이없네,,,