[프로그래머스] 사라지는 발판 (C++)

프로그래머스 사라지는 발판

1. 문제

문제 링크

2. 접근법

[ 문제 풀이 ]

 

위 문제는 2022 카카오 코딩 테스트에 출제된 문제이다.

 

board 의 크기가 크지 않기 때문에 완전 탐색을 이용하여 계산한다.

1. solve함수를 하나 선언하여 완전 탐색을 했다.

2. 재귀를 돌려야하기 때문에 우선 플레이어의 현재위치에 발판이 존재하는지 확인한다.

3. 플레이어가 현재 있는 위치에서 상, 하, 좌, 우 네 방향으로 이동할 수 있는지 판단한다.

4. 이동할 수 있다면 checked변수에 방문 표시를 하고 플레이어의 이동 횟수+1을 하여 다음 플레이어의 위치와 현재 플레이어의 위치를 매개변수로 하여 재귀 호출한다.

5. 재귀 호출의 종료 시점에 방문 체크를 다시 해제시키고(완전 탐색) 플레이어의 승패 여부를 경우의 수로 나눠 판단한다.

//현재 턴은 패배, 다음 턴은 승리인 경우
if (ans % 2 == 0 && cnt % 2 == 1)
	//바로 갱신
	ans = cnt;
//현재 턴은 패배, 다음 턴도 패배인 경우
else if (ans % 2 == 0 && cnt % 2 == 0)
	//최대한 늦게 지는 경우 선택
	ans = max(ans, cnt);
//현재 턴은 승리, 다음 턴도 승리인 경우
else if (ans % 2 == 1 && cnt % 2 == 1)
	//최대한 빨리 이기는 경우 선택
	ans = min(ans, cnt);

3. 코드

#include <string>
#include <vector>

using namespace std;
vector<vector<int>> map;
bool checked[5][5];
int dr[4] = { -1, 1, 0, 0 };
int dc[4] = { 0, 0, -1, 1 };
int n, m;
int solve(int currR, int currC, int nextR, int nextC)
{
    //발판이 사라졌다면
    if (checked[currR][currC])
        return 0;
    int ans = 0;
    //네방향으로 플레이어가 이동할 수 있는지 판단
    for (int dir = 0; dir < 4; ++dir)
    {
        int nr = currR + dr[dir];
        int nc = currC + dc[dir];

        if (nr < 0 || nr >= n || nc < 0 || nc >= m ||
            checked[nr][nc] || !map[nr][nc])
            continue;
        //플레이어가 이전에 있던곳에 방문표시
        checked[currR][currC] = true;
        int cnt = solve(nextR, nextC, nr, nc) + 1;
        checked[currR][currC] = false;

        //현재 턴은 패배, 다음 턴은 승리인 경우
        if (ans % 2 == 0 && cnt % 2 == 1)
            ans = cnt;
        //현재 턴은 패배, 다음 턴도 패배인 경우
        else if (ans % 2 == 0 && cnt % 2 == 0)
            //최대한 늦게 지는 경우 선택
            ans = max(ans, cnt);
        //현재 턴은 승리, 다음 턴도 승리인 경우
        else if (ans % 2 == 1 && cnt % 2 == 1)
            //최대한 빨리 이기는 경우 선택
            ans = min(ans, cnt);
    }
    return ans;
}
int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    int answer = -1;
    n = board.size();
    m = board[0].size();
    map = board;
    return solve(aloc[0], aloc[1], bloc[0], bloc[1]);
}

 

4. 결과