[BOJ] 사다리 조작 - DFS

15684: 사다리 조작 골드4 아 어려웠다.

import sys
input = sys.stdin.readline
from collections import deque

nvertical, nline, nhorizontal = list(map(int, input().split()))
toRight = set()

for _ in range(nline):
    hor, ver = list(map(int, input().split()))
    toRight.add((ver-1,hor-1))

v = deque([])
v.append((0, 0,0, set()))
answer = -1
while v:
    start, ver, hor, toR= v.pop()
    if hor == nhorizontal:
        if start == ver:
            if start == nvertical - 1:
                answer = len(toR)
                break
            else:
                v.append((start+1, start+1, 0, toR))
        continue
    while hor < nhorizontal:
        if (ver,hor) in toR or (ver,hor) in toRight:
            ver+=1
            hor+=1
            if hor == nhorizontal:
                v.append((start, ver, hor, toR))
        elif (ver-1, hor) in toR or (ver-1,hor) in toRight:
            ver-=1
            hor+=1
            if hor == nhorizontal:
                v.append((start, ver, hor, toR))
        else:
            if ver - 1 >= 0 and (ver-2, hor) not in toR and (ver-2, hor) not in toRight and len(toR) < 3: # 하나 빼줘도 될듯
                v.appendleft((start, ver-1, hor+1, toR | {(ver-1, hor)}))
            # 오른쪽
            if ver + 1 < nvertical and (ver+1,hor) not in toR and (ver+1, hor) not in toRight and len(toR) < 3:
                v.appendleft((start, ver+1, hor+1, toR | {(ver, hor)}))
            # 아래로 이동
            v.append((start, ver, hor+1, toR))
            break
print(answer)

아 너무 어려웠다.. 시간초과가 많이 났다. 보니까 대부분 PyPy3 로 해서 통과하고 Python3로 통과한 사람은 몇 없더라.

일단 기본 구조는,
toRight 는 사다리의 왼쪽 끝의 집합들이다.

---

while hor < nhorizontal:
      if (ver,hor) in toR or (ver,hor) in toRight:
          ver+=1
          hor+=1
          if hor == nhorizontal:
              v.append((start, ver, hor, toR))
      elif (ver-1, hor) in toR or (ver-1,hor) in toRight:
          ver-=1
          hor+=1
          if hor == nhorizontal:
              v.append((start, ver, hor, toR))
      else:
          if ver - 1 >= 0 and (ver-2, hor) not in toR and (ver-2, hor) not in toRight and len(toR) < 3: 
              v.appendleft((start, ver-1, hor+1, toR | {(ver-1, hor)}))
          # 오른쪽
          if ver + 1 < nvertical and (ver+1,hor) not in toR and (ver+1, hor) not in toRight and len(toR) < 3:
              v.appendleft((start, ver+1, hor+1, toR | {(ver, hor)}))
          # 아래로 이동
          v.append((start, ver, hor+1, toR))
          break
print(answer)

현재 세로선과 가로선 인덱스(ver, hor) 에 대하여
만약 오른쪽으로 가는 가로선이 있으면 오른쪽 하단으로 이동하고, 왼쪽으로 가는 가로선이 있으면 왼쪽 하단으로 이동하는 과정을 반복한다. (이동할 수 있는 선택권이 없는 상황)
현재 ver,hor 좌표에 아무 가로선이 없으면 1. 가로선을 왼쪽으로 생성하거나, 2. 가로선을 오른쪽으로 생성하거나, 3. 가로선 생성 없이 밑으로 내려가기 의 세 가지 방법이 있다.
while 문 내 if 문에서 else 문이 이에 대한 코드이다.

여기에서 시간을 줄여주기 위하여 가로선이 현재보다 늘어나면 v 왼쪽에 추가하고, 현재와 동일하면 v 오른쪽에 추가하는 방식을 추가했다. 이렇게 해주면 가장 작은 가로선 개수에 대해 먼저 탐색하게 되므로 원하는 조건을 충족하는 답이 나왔을 때 바로 답을 print 하고 다른 경우의 수를 살펴보지 않아도 된다.

---

위 코드의 상단에는

while v:
    start, ver, hor, toR= v.pop()
    if hor == nhorizontal:
        if start == ver:
            if start == nvertical - 1:
                answer = len(toR)
                break
            else:
                v.append((start+1, start+1, 0, toR))
        continue

계속해서 밑으로 나아가던 (ver,hor) 에 대하여 만약 hor == nhorizontal(가로선 최대)이면 (가로선 끝까지 좌표가 이동했다면) 현재 세로선이 시작한 세로선과 동일한 지 확인해준다.(i번 세로선 결과가 i이어야 함)

그러한 경우에는 원하는 조건을 만족하므로 다음 세로선의 처음부터 사다리타기를 시작한다. (v.append 부분)
만약 start == nvertical - 1 이면 (마지막 세로선까지 탐색이 끝났다면, 사실 마지막 세로선은 검사 안해줘도 된다) 탐색을 멈추고 답을 출력한다.