백준 15684번: 사다리 조작 (c++)

[문제 링크]

15684번: 사다리 조작

---

생각해야 될 것이 두가지 정도 있다고 생각한다.

1. 현재 위치에서 사다리가 연결되어있는지 안되어있는지 어떻게 확인할 것인가?

--> 사다리의 bool형 2차원 배열을 만들어 false로 초기화하고 연결된 지점을 true로 설정함

2. 현재 위치가 연결된 지점(true)이라면 왼쪽으로 갈 것인가? 오른쪽으로 갈 것인가?

--> 이 부분에서 오래 고민했다. A >>> B 방향으로 가는 사다리가 있을 때 A지점만 true로 설정해준다음 사다리를 타는 함수에서는 (현재 row좌표 - 1) 좌표가 true인지 확인하고 true라면 왼쪽으로 이동, true가 아니고 현재 지점이 true라면 오른쪽으로 이동하도록 구현하였다.

 

이정도만 주의해서 구현 시킨다면 무난히 해결할 수 있을 것이다. 연결이 안된부분에 사다리를 1개~3개까지 놓는 모든 경우의 수에 대하여 사다리가 1:1매칭이 되는지 안되는지 확인하고 가장 적은 갯수를 반환해주면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
#include <cstring>
using namespace std;
 
const int INF = 987654321;
bool ladder[31][11];
int col, row;
inline int min(int a, int b) { return a < b ? a : b; }
bool SuccessCheck()    // 사다리가 1:1 매치가되는지 확인
{
    for (int i = 1; i <= row; i++)
    {
        int start = i; // 시작할 위치(row) 저장
        for (int j = 1; j <= col; j++)
        {
            if (ladder[j][start - 1])
                start--;
            else if (ladder[j][start])
                start++;
        }
        if (start != i) return false;
    }
    return true;
}
int Solution(int startY, int startX, int pick)
{
    if (SuccessCheck()) return pick; // 기저사례. 사다리가 1:1매칭된다면 pick값 반환
    if (pick == 3) return INF; // 기저사례. 사다리 3개 추가했는데 위에 기저사례를 통과 못했으므로 무조건 불가능함
    int ret = INF;
    for (int i = startY; i <= col; i++)
        for (int j = 1; j <= row; j++)
        {
            if (startY == i && startX > j) continue; // 중복탐색 제거
            if (!ladder[i][j] && !ladder[i][j - 1] && !ladder[i][j + 1]) // 탐색지점 좌우측에 이미 사다리가 연결되었다면 사다리 생성 불가
            {
                ladder[i][j] = true;
                ret = min(ret, Solution(i, j, pick + 1));
                ladder[i][j] = false;
            }
        }
    return ret;
}
int main(void)
{
    int ldNum;
    cin >> row >> ldNum >> col;
    memset(ladder, false, sizeof(ladder));
    while (ldNum--)
    {
        int c, r;
        cin >> c >> r;
        ladder[c][r] = true;
    }
    int result = Solution(0, 0, 0);
    if (result == INF)
        cout << -1 << endl;
    else
        cout << result << endl;
    return 0;
}

 

 

알고리즘 200일 프로젝트 - 17day

내일도 열심히!