백준 사다리조작 파이썬

 

15684번: 사다리 조작

 

1. 조건

- 최대 3개까지 가로선 추가, 3개를 넘으면 -1 출력

- 두 가로선이 접하면 안된다.

- 모두 i -> i 번 도착해야한다.

2. 구하고자 하는 것

- 모든 1~n번 세로선이 사다리를 타고 i->i 으로 도착할 수 있도록, 추가해야하는 가로선 개수 최솟값.

3.  가로선 선택 부분 풀이 및 설계

완전 탐색으로, 10*30 => 가로선이 접하면 안된다는 조건 하에서, 약 300개 중에서 최대 3개를 고르는 조합이라고 볼 수 있다.

300C3 * 300(체크하는 함수) => 기본적으로 1억이 넘는다.

중간에 서로 선이 접하면 안되는 조건도 있지만 그래도! 최적화를 좀 해야함.

ex) 최적화는, 최대 3개이므로 이 그 이상의 깊이는 조사하지 않는다던지.

이 문제는 2차원 배열의 지점을 선택하기에, for중복문을 사용해서 선택할 가로선을 정할 수 있는데, 

for i in range(1,h+1):
	for j in range(1,n+1):
    	if # 조건문:
        	line[i][j]=1
        	dfs(total+1,,,,)
            line[i][j] = 0

보통 위의 형태로 코드를 쓸 수 있다. 하지만 최적화를 위해 일반 for중복문에서 좀 더 생각해보자.

backtracking을 한다면 아마, 끝까지 depth까지 들어가면 열 선택이 끝나서 이전 함수 호출로 돌아갈 것이다. 그러면?

다음 행 부터 선택할 수 있게 되고 이때는 당연히 1번 열부터 탐색을 해야한다. 하지만, 계속 쭉 재귀호출로 depth가 커지고 있는 상태라면?

굳이 1부터 탐색할 것이 아니라, 이어서 탐색해야하지 않겠는가, 지금 행에서 1번 열은 이미 전부터 탐색했는데?!

또한 두 가로선이 접하고 이어지면 안되기 때문에 선택한 부분으로부터 다 다음 부터 선택 가능하다.

이를 반영하면 대략 아래와 같은 코드를 생각할 수 있다.

def dfs(total, x,y):
	#	,,,,,,
    	#	,,,,,,
    for i in range(1,h+1):
        if x == i:
            col = y # 아직 같은 행 탐색 중이면 y부터
        else:
            col = 1 # 다른 행 탐색 중이면 1부터 다시.
        for j in range(col,n+1):
            if # 조건문:
                line[i][j]=1
                dfs(total+1,i,j+2)
                line[i][j] = 0

조합 문제로, 라이브러리로 풀 수도 있지만, 삼성문제에서는 라이브러리 사용 금지.

**조합은 DFS로 풀 때, 보통 함수의 매개변수로 다음부터 선택할 수 있는 범위를 전달하는 방식으로 코드를 만들더라.

이 풀이는 pypy로 통과함.

코드

answer = 4 # 최대 3개까지 설치 가능하기 때문에 큰 값 4를 할당.
n,m,h = map(int,input().split())# 열, 가로선 개수, 행 입력.
line = [[0]* (n+1) for _ in range(h+1)]# 1번 ~ n번 열, 1~h번 행.

for _ in range(m):
    a,b = map(int,input().split())
    line[a][b]=1 # a번행의 b열와 b+1열이 연결 되있음.

def check():# 모든 1~n번이 i -> i 로 도착하는지 체크.
    for x in range(1,n+1):
        now = x # 현재 i번 시작점.
        for r in range(1,h+1): # row 한칸씩 내려감.
            if now > 1 and line[r][now-1]:# 만약 왼쪽에 사다리가 있다면 이동.
                now -= 1
            elif line[r][now]:# 만약 오른쪽에 사다리가 있다면 이동
                now += 1
        if x == now:# 이동후에 i -> i 번이라면, 계속 진행
            continue
        else: # 하나라도 아니라면 False 반환.
            return False

    return True # 모두 i-> i번도착 True .

def dfs(total,x,y):# 추가할 사다리 개수 세기
    global answer,line
    if check(): # 모두 i -> i번 도착인지 체크.
        answer = min(answer,total) # answer update.
        return
    
    if total >= 3 or total>=answer: # 만약 현재까지 세는 개수가 3 이상이라면 그만두기, 또는 이미 answer 이상으로 크다면 그만.
        return
     
    for i in range(x,h+1):# 행
        if x == i:
            col = y # 아직 같은 행 검사 중이라면, 매개변수 이어서 y할당
        else:
            col = 1 # 백트래킹으로 다음 행 검사를 한다면, 열은 1부터 다시 탐색.
        for j in range(col,n):# 가로선이 이어지면 안되므로, 체크.
            if not line[i][j] and not line[i][j-1] and not line[i][j+1]:
                line[i][j] =1 # 선택.
                dfs(total+1,i,j+2) # 다 다음 열부터 탐색 가능.
                line[i][j] = 0 # 백트래킹으로 다시 0 할당.
dfs(0,1,1) # (1,1)부터 선택 시작! => 전체 가능한 것 중에서 최대 3개를 뽑는 것이므로 조합. 조합은
# 매개변수에 인덱스를 넣으면서 범위를 좁혀간다.
if answer > 3: # 3보다 크면 -1
    print(-1)
else:
    print(answer)

완탐은 조합, 순열 자주 나옴! 💪