개발자가 되기로 마음먹은지 3년 째...
백준 알고리즘에서 입력도 못하던 시절도 있었고, 카카오 코딩테스트에서 1번 문제도 못풀었던 시절이 엊그제 같은데... 이제는 어느정도 코테는 자신있을 정도로 많이 연습을 했다. 그러나 여전히 높은 난이도의 코테(특히 카카오..)는 붙지도 못하니 그냥 알고리즘 문제 푸는 것보다 이렇게라도 기록을 남겨 복습하고 머리에 남겨놔야겠다는 생각으로 알고리즘 1일차를 시작하려 한다.
(참고로 필자는 백준 골드 1이지만 실력은 골드 3~4라고 생각..)
그럼 첫 스타트 깔쌈하게 시작할 겸 야무진 문제로 오늘 하루 풀어보자!
문제 : https://www.acmicpc.net/problem/15684
흔히 아는 사다리게임의 규칙이 적용되고, 문제에서 요구하는 것은 모든 번호가 자기 번호로 매칭되도록 추가하는 가로선의 최소한의 개수를 구하는 것이다.
일단 n,m,h와 가로선의 정보를 토대로 board를 구성해보자.
나는 2차원 행렬로 선언하되 세로선들 사이에 빈칸을 넣어주는 방식으로 행렬을 만들어 주었다
예를 들어, n=2,m=1,h=3 라면 5(h+2)x4(n*2) 행렬로 만들어 주는 것이다
1,0,1,0
1,0,1,0
1,0,1,0
1,0,1,0
1,0,1,0
이런식으로 만들고 중간에 주어진 가로선의 정보를 넣어주어 board를 만든다.
예를 들어 가로선 1개(m)에 대하여 a=1,b=1이 주어졌다면 위 board는 다음과 같이 된다.
1,0,1,0
1,1,1,0
1,0,1,0
1,0,1,0
1,0,1,0
이제 board를 만들었으니 내가 생각한 알고리즘을 생각하겠다.
처음엔 dfs + combinations 를 생각했으나 역시나 시간초과가 떴다...
두번 째 방법으로는 combinations를 만들 때 문제 조건인 "연속으로 가로선이 연결될 수 없다"를 이용하여 combinations를 통해 나온 후보들을 줄였지만 이 또한 시간초과가 났다...
경우가 0,1,2,3 까지만 고려하면 되니 모든 탐색을 진행하려 했는데 어디서 잘못한 것일까...
combination이고 뭐고 그냥 bfs + 백트래킹으로 전체탐색을 한번 해보자
#from itertools import combinations
n,m,h = map(int,input().split())
board = [[0] * (2*n) for _ in range(h+2)]
for j in range(0,2*n,2):
for i in range(h+2):
board[i][j] = 1
for _ in range(m):
a,b = map(int,input().split())
board[a][2*b-1]=1
#flag = False
def check(board): # 모든 idx가 각자의 idx인지 확인
for i in range(0,2*n,2):
cur = i
result = True
for j in range(0,h+2):
if j==h+1:
if cur!=i:
result = False
#여기서 중요한 것은 오른쪽 왼쪽 or 왼쪽 오른쪽 탐색 후 있으면 무조건 가야됌
if cur+2<2*n and board[j][cur+1] == 1:
cur+=2
elif cur-2>=0 and board[j][cur-1] == 1:
cur-=2
if not result: # 하나라도 자기 idx와 다른 위치로 갈 경우 False 반환(5줄 위 코드 참고)
return False
return True
answer = 99999999
def solution(y,cnt):
global answer
if cnt>3 or answer<=cnt: # 불필요한 경우 걸러줌
return
if check(board): # check 확인
answer = min(answer, cnt)
return
for i in range(y,h+1): # 여기서 y가 아닌 1로 할 경우 시간초과
for j in range(1,2*n,2):
possible = True
if board[i][j]!=0:
possible=False
if j+2<2*n:
if board[i][j+2]!=0:
possible = False
if j-2>=0:
if board[i][j-2]!=0:
possible = False
if possible:
board[i][j]=1
solution(i,cnt+1)
board[i][j]=0
solution(1,0)
if answer == 99999999:
print(-1)
else:
print(answer)위 코드에서 가장 중요한 부분은 solution 함수에서 1부터 h+1까지가 아닌 y부터 h+1로 한 것이다. 생각을 해보면 이미 지나간 구간을 굳이 한번더 살펴볼 필요가 없는데 이걸 생각 못하고 매번 dfs호출할때마다 모든 영역을 다 탐색했고, 결국 저것땜에 필자는 시간초과가 계속났다...
후... 한 문제 푸는데 1시간 이상 걸렸다...
