C++/ 26169 / 세 번 이내에 사과를 먹자 ( 백트래킹 )

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

문제 요약

5 x 5 크기의 보드가 주어집니다.

보드는 1 x 1 크기의 정사각형 격자로 이루어져 있습니다.

보드의 격자는 사과가 1개 있는 격자, 장애물이 있는 격자, 빈칸으로 되어 있는 격자로 구분됩니다. 격

자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호를 나타냅니다.

행 번호는 맨 위 위치가 0이고 아래 방향으로 1씩 증가합니다.

열 번호는 맨 왼쪽 위치가 0이고 오른쪽으로 1씩 증가합니다.

즉, 맨 왼쪽 위 위치가 (0, 0), 맨 아래 오른쪽 위치가 (4, 4)입니다.

현재 한 명의 학생이 (r, c) 위치에 있고 한 번의 이동으로 상, 하, 좌, 우 방향 중에서 한가지 방향으로 한 칸 이동할 수 있습니다.

학생이 사과가 있는 칸으로 이동하면 해당 칸에 있는 사과를 1개 먹습니다.

장애물이 있는 칸으로는 이동할 수 없습니다.

학생이 지나간 칸은 학생이 해당 칸을 떠나는 즉시 장애물이 있는 칸으로 변경됩니다.

즉, 학생이 해당 칸에서 상, 하, 좌, 우 방향으로 한 칸 이동하는 즉시 해당 칸은 장애물이 있는 칸으로 변경됩니다.

학생이 현재 위치 (r, c)에서 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을 출력하고, 그렇지 않으면 0을 출력해야합니다.

문제 풀이

1. 보드를 입력받습니다.

2. 시작 위치를 입력받습니다. 시작 위치가 사과가 있는 위치이면 개수를 하나 세어 줍니다.

3. dfs 함수를 돌리는데, 함수에 들어왔을때 방문처리를 해줍니다. ( 첫번째 노드도 방문처리를 하기 위해 )

4. dfs 함수의 매개변수로는 좌표 y, x와 스텝의 수 사과의 수를 받습니다.

5. 탐색을 하는데 -1이면 장애물이기 때문에 무시하고 1이면 사과이기 때문에 스텝과 사과를 증가시켜 탐색을 합니다.

6. 사과가 아닌 칸은 스텝만 증가시킵니다.

7. 탐색을 마치면 백트래킹 ( 방문 처리 false )를 하여 해당 노드에서 갈 수 있는 다른 길을 탐색합니다.

8. 매개변수로 받는 스텝이 3보다 커지면 리턴하고 사과의 개수가 2개 이상 이면 정답 변수에 1을 저장합니다. ( 사과의 개수가 안모이면 초기값 0 )

9. 정답 변수를 출력합니다.

 

주의할 점

처음에는 bfs 문제로 생각하였습니다. 

하지만 그렇게 되면 사과의 개수를 제대로 셀수 없게 됩니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

vector<vector<int>> v;
vector<vector<int>> ans;
bool visit[100][100];
int r, c, cnt = 0;

void dfs(int y, int x, int num, int apple)
{
    visit[y][x] = true;
    if (num > 3)
    {
        return;
    }
    if (apple >= 2)
    {
        //cout << y << " " << x << "\n";
        //cout << apple << "    ";
        cnt = 1;
    }
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= 5 || ny < 0 || nx >= 5 || nx < 0)
        {
            continue;
        }
        if (visit[ny][nx])
        {
            continue;
        }
        if (ans[ny][nx] == -1)
        {
            continue;
        }
        if (ans[ny][nx] == 1)
        {
            dfs(ny, nx, num + 1, apple + 1);
            visit[ny][nx] = false;
        }
        else
        {
            dfs(ny, nx, num + 1, apple);
            visit[ny][nx] = false;
        }


    }

}


int main()
{
    int a = 0;
    v.resize(5, vector<int>(5));
    ans.resize(5, vector<int>(5));
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            cin >> ans[i][j];
            v[i][j] = 0;
        }
    }

    cin >> r >> c;
    if (ans[r][c] == 1)
    {
        a += 1;
    }
    dfs(r, c, 0, a);
    cout << cnt;
    return 0;
}

반응형

예제1

0 0 1 0 0
0 0 -1 0 0
0 0 1 0 0
1 1 -1 1 0
0 0 0 -1 0
4 1

결과 1

예제2

0 0 1 0 0
0 0 -1 0 0
0 0 1 0 0
1 0 -1 1 0
0 0 0 -1 0
2 3

결과 2