백준 15684번 사다리 조작 C++

 

1. 문제 설명

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다.

인접한 세로선 사이에는 가로선을 그을 수 있는데

각각의 세로선 마다 가로선을 그을 수 있는 위치의 개수를 H이고

모든 세로선이 같은 위치를 갖는다.

 

가로선은 연속하거나 서로 접하게 그을 수는 없다.

주어진 사라디에 가로선을 추가하여 사다리 게임의 결과를 조작하려고 하는데

 i번 세로선에서 출발하면 i번 세로선으로 도착하도록 할려고 한다.

그렇게 사다리를 조작하였을 때 추가해야 하는 가로선의 최솟값을 구하는 프로그램을 작성해라

단 그을 수 있는 가로선은 4개 이상 나올 수 없으며 4개 이상 나온다면 -1을 출력해라

 

첫째 줄에 세로선 N, 가로선의 개수 M, 그을 수 있는 가로선 위치 개수 H가 주어진다.

가로선의 정보는 두 정수 a와 b로 나타내고 , b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

 

초기 사다리 입력값을 받기 위해 n,m,h를 받고

for문을 통해 ladder 이중벡터를 만들어 사다리 정보를 담아준다.

 

그다음 dfs함수 구문으로 들어간다. 

 

correct함수를만들어  현재 사다리판 상태에서 모든 세로선 i가 i번에 도착하는지 확인을 한다.

사다리를 내려가며 좌우 이동이 필요한 경우 처리를 해주고

오른쪽에 연결된 사다리면 열에 + 1 

왼쪽이면 열 - 1을 해준다.

도착한 세로선 번호가 시작번호와 다른 경우 false 반대면 treu로 해주며

dfs를 실행한다.

 

dfs에서는 행과 열을 순회하며 

이동 가능한 경우를 따지고 사다리에 가로선을 추가하며 재귀를 이용해 검사해주고,

실패하면 백트래킹을 이용해 사다리를 원상 복구하고 다음 작업을 이어간다.