[백준 15684] 사다리 조작

[ 백준 15684 : 사다리 조작 ]

삼성 공채 기출문제다.
조합+탐색 문제였다.
일단 내가 푼 방식은 이렇다.

mat[35][12][12] 변수를 두고 처음 입력받는 사다리들을 저장한다.
만약 첫번째 가로선에 세로선 1과 2가 연결되어있다고 입력되면
mat[1][1][2] = mat[1][2][1] = 1 이렇게 저장된다.
또는 세번째 가로선에 세로선 3과 4가 연결되어있다면
mat[3][3][4] = mat[3][4][3] = 1 이런식으로 연결된 사다리가 저장된다.

그 다음은 연결 할 수 있는 사다리를 찾는다.
최악의 경우에 사다리는 300개보다 작다. 왜냐하면 같은 가로선에서 연속적으로는 사다리를 놓을 수 없기때문이다.
최악에 한 층에 5개씩만 사다리가 저장되니 5*30 약 150개의 놓을 수 있는 좌표를 만들 수 있다.

만드는 법은 간단한데 그냥 for문을 i : 1~h 그리고 j : 1~n 을 보면서
mat[가로][세로][세로+1] == 0 and mat[가로][세로][세로-1] == 0 && mat[가로][세로+1][세로+2] == 0
라면 따로 배열에 i와 j를 저장해 놓는다.
이 배열을 ladder라고 저장해놓았다.

그 다음으로는 사다리를 놓기만 하면된다.
재귀함수를 만들었는데 void sol(int idx, int pidx,int tidx) 에서
idx는 현재 사다리를 놓은 갯수이다.
pidx는 사다리를 몇 개까지 놓을 수 있는지의 갯수이다.
tidx는 현재 ladder배열의 좌표이다.

sol함수의 내부는 현재 놓은 사다리가 출력 조건에 맞는지를 보는 부분, 사다리를 놓는 부분 이렇게 두가지로 구현되어져있다,

변수들이 조금 복잡해서 나도 헷갈렸는데 이런 변수이름도 좀 제대로 알기쉽게 선언하는 습관을 들여야겠다.