백준 구현 대비 사다리 조작

문제 : https://www.acmicpc.net/problem/15684

접근

추가 사다리의 갯수가 4개 이상이 되거나 사다리를 어떤 식으로 조작해도 각각의 세로선이 일치하지 않으면 -1을 출력한다. 즉 추가 사다리 경우의 수를 0~3까지 combintaion연산 후 각각의 경우를 계산해주면 된다.
초기에는 사다리로 연결되어있는 그래프의 두 점을 모두 1로 설정해주었는데 이 잘못된 접근 때문에 시간이 꽤 많이 걸렸다. 문제가 발생하는 에시는 다음과 같다.

예를들어 사다리가 다음과 같이 연결되어 있을때
o----o      o----o

이를 그래프로 표한혀면 [1,1,1,1]로 표현되고 이는
o----o-----o----o
과 구별할 수 없게 된다.
즉 사다리를 표현하려면 사다리의 두 좌표중 작은 지점을 1 큰 지점을 0으로 표현해야 모든 사다리의 경우의 수를 다 중복없이 표현할 수 있게된다.
다음부터 이거와 비슷한 문제 나오면 유념해야 할듯.

from itertools import combinations
def check(visit):    #300
  for i in range(H):
    for j in range(N-1):
      if visit[i][j]==1 and visit[i][j+1]==1:
        return False
  return True

def route(graph,num):  # 40
  i,j=0,num
  while i<H:
    if graph[i][j]==1:
      i+=1
      j+=1
    else:
      if 0<=j-1<N and graph[i][j-1]==1:
        j-=1
        i+=1
      else:
        i+=1
    
  if num==j:
    return True
  else:
    return False

answer=4
flag=False
N,M,H=map(int, input().split())
graph=[[0 for i in range(N)] for j in range(H)]
lines=[]
add=[]
addcomb=[]
for i in range(M):
  lines.append(list(map(int,input().split())))

for line in lines:
  a,b=line[0],line[1]
  graph[a-1][b-1]=1

for i in range(H):
  for j in range(N-1):
    if graph[i][j]==0 :
      add.append([i,j])

for i in range(4):
  if flag:
    break
  addcomb=list(combinations(add,i))
  for aaa in addcomb:
    if flag:
      break
    tempgraph=[item[:] for item in graph]
    checked=True
    for aa in aaa:
      tempgraph[aa[0]][aa[1]]=1

    if check(tempgraph):
      for j in range(N):
        if route(tempgraph,j):
          continue
        else:
          checked=False
          break
      if checked:
        flag=True
        print(i)
        break
    else:
      continue

if not flag:
  print(-1)