import sys
from copy import deepcopy
def i_is_i(ladder):
for i in range(N): # i가 i로 가는지 확인한다
col = i
for row in range(H): # 마지막 가로줄(H) 가기 전까지 확인
if ladder[row][col]: # col번 세로선과 col+1번 세로선이 row번 가로선에 의해 연결되는가?
col += 1 # 다음 세로줄로 이동
elif 0 < col and ladder[row][col-1]: # col-1 세로선과 col 세로선이 row 가로선에 의해 연결되는가?
col -= 1
if col != i:
return False
return True
def dfs(idx, count, max_count, ladder):
if count == max_count:
if i_is_i(ladder):
print(max_count)
exit(0)
return
for i in range(idx, H): # 가로. '조합'이므로 idx를 정하고 한 번 뽑은건 더이상 보지 않도록 한다
for j in range(N-1): # 세로
if ladder[i][j] != 1:
if 0 < j and ladder[i][j-1] == 1:
continue
if j < N-1 and ladder[i][j+1] == 1:
continue
ladder[i][j] = 1
dfs(i, count+1, max_count, ladder)
ladder[i][j] = 0
if __name__ == '__main__':
input = sys.stdin.readline
N, M, H = map(int, input().split()) # 세로선, 가로선, 가로선후보갯수
ladder_origin = [[0] * N for _ in range(H)]
for _ in range(M):
i, j = map(int, input().split()) # j번 세로줄과 j+1번 세로선을 i번째 가로선이 연결하고 있음
ladder_origin[i-1][j-1] = 1 #
for h_num in range(4): # 가로줄을 0~3개 놓아봄
dfs(0, 0, h_num, deepcopy(ladder_origin))
print(-1)
처음 문제를 보자마자 멘붕에 빠지게했던 문제.
보통 완전탐색이나 DFS, BFS 문제는 '칸'을 탐색하게 되는데 이 문제는 line을 따라서 탐색하라고 하고 있었다.
하지만 이게 헷갈렸던 이유는 문제를 끝까지 안 봐서 그렇다.
가로선의 정보는 두 정수 a과 b로 나타낸다. b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.
라고 문제에 분명히 나와있기 때문이다.
즉 ladder 라는 이중 리스트를 만들고, ladder[a][b] 는 사다리에서 b와 b+1 세로선 사이에 a 가로선이 있다, 라고 생각하면 되는 것이다.
구글링해보면 a와 b를 반대로 쓴 사람이 많긴 한데 나는 실제 사다리 모양과 일치시키고 싶어서 row를 가로선으로, column을 세로선으로 놓고 풀었다.
이 문제의 정답률이 낮은 이유는 첫째 '칸' 대신 'line'을 탐색하기 때문에 헷갈려서, 둘째는 시간초과가 나서 그런 것 같다. 이를 해결하기 위한 방법은 대충 몇 가지가 있다.
- 일단 주어진 사다리를 내려가는 함수부터 만들어본다.
- 그 다음 가로선을 추가하는 함수를 만들어본다.
- 둘을 연결한다.
시간초과를 줄일 수 있는 방법은...
- 놓을 수 있는 '최소' 가로선의 갯수를 구하라고 했으므로 0부터 3까지 가로선의 갯수를 올려가면서 알고리즘이 실행되도록 하고 i=i인 경우가 나온다면 곧바로 종료한다. 예를 들어 0에서 i=i인 경우가 나왔으면 1~3은 보지 않아도 되는 것.
- 놓을 가로선을 뽑을 때 순열이 아닌 조합으로 뽑는다. <-당연한건데 본인은 이것 때문에 한참 헤맸다. 25 line 참고.
- 놓을 가로선을 뽑을 때 사다리 배열을 deepcopy 해서 재귀호출하지 말고, 가로선 check->DFS호출->가로선 uncheck 식으로 진행한다.
- i_is_is 함수는 실제로 사다리를 내려가보면서 i=i인지 확인하는 함수인데, i != i인 경우가 나오면 더이상 남은 세로선은 시도하지 않고 바로 종료하도록 한다.