[백준/c++] BOJ 26169 - 세 번 이내에 사과를 먹자

https://www.acmicpc.net/problem/26169

26169번: 세 번 이내에 사과를 먹자

 

문제 설명

5x5 크기의 보드에 1 (사과가 있는 칸), 0 (비어 있는 칸), -1 (장애물이 있는 칸) 이 있다. 상, 하, 좌, 우 중 한 가지 방향으로 이동했을 때, 이동한 칸에 사과가 있다면 해당 칸에 있는 사과를 1개 먹는다. 지나간 칸은 즉시 장애물이 있는 칸으로 변경된다. 세 번 이하의 이동으로 사과 2개 이상을 먹을 수 있으면 1을 출력하고, 그렇지 않으면 0을 출력한다.

 

해결

간단한 백트래킹 문제이다.

cnt (몇 번 이동하였는지를 저장) 가 3이면, 3번 이동한 것이므로 dfs 함수를 끝낸다.

dfs에 들어가기 전에는 해당 칸을 visited == 1로 만들어 주고, dfs가 끝났을 때 다시 visited == 0으로 돌려 주어야 한다.

또한 해당 칸이 1 (사과가 있는 칸)이라면, 사과의 개수를 증가시켜 준다.

 

오랜만에 백트래킹 문제를 풀었더니 좀 헤맸는데, 시작 지점의 visited를 1로 해 주지 않아서 틀리고 있었다. ㅜ

코드

#include<bits/stdc++.h>
using namespace std;

int board[6][6];
int a, b, ans = 0;
int visited[6][6];
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0 ,0, 1, -1 };

int range_over(int x, int y) {
    return x < 0 || y < 0 || x >= 5 || y >= 5;
}

void dfs(int x, int y, int cnt, int apple) {
    if (cnt == 3) {
        if (apple >= 2) ans = 1;
        return;
    }
    int ap = apple;
    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir], ny = y + dy[dir];
        if (range_over(nx, ny) || visited[nx][ny] || board[nx][ny] == -1) continue;
        visited[nx][ny] = 1;
        if (board[nx][ny] == 1)
            dfs(nx, ny, cnt + 1, ap + 1);
        else
            dfs(nx, ny, cnt + 1, ap);
        visited[nx][ny] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++)
            cin >> board[i][j];
    }

    cin >> a >> b;
    visited[a][b] = 1;
    dfs(a, b, 0, 0);
    cout << ans;
}