[백준_14890(경사로)]

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

14890번: 경사로

문제

문제 풀이

• 단순 시뮬레이션 문제이다.(모든 경우를 다 나열해도 시간에 영향 없다.)
• 행과 열의 경사로는 별개이다.(이건 왜그런지 이해 못하겠음...)
• 행 과 열을 각각 탐색해야한다.

순서

1. 열과 행 기준으로 각각 탐색한다.
2. 탐색하는 방향 기준으로 다음 행 혹은 열이 평평한 지 차이가 나는 지 탐색
   • 평평하다면 통과
   • 차이가 1이 아니라면 종료
   • 차이가 1 나면 3번 단계 진행
3. 좌우 혹은 상하로 각각 경사로를 놓을 수 있는 지 탐색하가.
   • 탐색하며, 평평하지 않는경우 or 범위에서 벗남 or 이미 경사로가 놓아져 있다면 종료
   • 놓을 수 있다면 각 좌표에 경사로를 놓아 준다.
4. 탐색하는 행 혹은 열이 경로가 된다면 카운팅 해준다.

 

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int p[101][101];
int n, l;
int visited[101][101];

bool check_num(int x, int y) //범위 넘어가는지 체크
{

    if (x >= 0 && x < n && y >= 0 && y < n)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool lean_go(int x, int y, int move_y, int move_x) //사다리 놓을 수 있는 지 체크

{
    int ki = p[x][y];
    vector<pair<int, int> > v;

    for (int i = 0; i < l; i++) //경사로 길이만큼 탐색
    {
        if (p[x][y] != ki || !check_num(x, y) || visited[x][y])
        {
            //기준점과 같이 않거나(평평한지),범위를 넘어가거나,이미 경사로를 놓았다면
            int temp = !check_num(x, y);

            return false;
        }
        else
        {
            v.push_back(make_pair(x, y)); ///가능 하면 좌표 추가
        }
        y += move_y; //행에 경사로 놓을때,
        x += move_x; //열에 경사로 놓을때
    }

    if (v.size() == l)
    {
        for (int i = 0; i < v.size(); i++) //사다리 놓음
        {

            visited[v[i].first][v[i].second] = 1;
        }
    }
    else
    {
        return false;
    }
    return true;
}

int main()
{

    cin >> n >> l;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {

            cin >> p[i][j];
        }
    }

    memset(visited, 0, sizeof(visited));

    int ans = 0;
    for (int i = 0; i < n; i++) //행 기준 탐색
    {
        bool check = true;

        for (int j = 0; j < n - 1; j++)
        {
            if (p[i][j] == p[i][j + 1]) //평평하면 통과
            {
                continue;
            }
            else
            {

                if (abs((p[i][j] - p[i][j + 1])) == 1) //차이가 1이면
                {
                    if (p[i][j] > p[i][j + 1]) //오른쪽에 경사로 놓는경우
                    {

                        if (!lean_go(i, j + 1, 1, 0)) //행애 오른쪽에 놓음
                        {

                            check = false;
                            break;
                        }
                    }
                    else
                    { //왼쪽에 경사로 놓는경우

                        if (!lean_go(i, j, -1, 0)) //행애 왼쪽에 놓음
                        {

                            check = false;
                            break;
                        }
                    }
                }
                else
                {
                    check = false;
                    break;
                }
            }
        }
        if (check)
        {
            ;
            ans += 1;
        }
    }

    memset(visited, 0, sizeof(visited)); //경사로 초기화

    for (int j = 0; j < n; j++) //열 기준 탐색
    {
        bool check = true;

        for (int i = 0; i < n - 1; i++)
        {

            if (p[i + 1][j] == p[i][j])
            {
                continue;
            }
            else
            {

                if (abs((p[i][j] - p[i + 1][j])) == 1)
                {
                    if (p[i][j] > p[i + 1][j])
                    {

                        if (!lean_go(i + 1, j, 0, 1)) //열에 앞쪽에 놓음
                        {

                            check = false;
                            break;
                        }
                    }
                    else
                    {

                        if (!lean_go(i, j, 0, -1)) //열에 뒷쪽에 놓음
                        {

                            check = false;
                            break;
                        }
                    }
                }
                else
                {
                    check = false;
                    break;
                }
            }
        }
        if (check)
        {

            ans += 1;
        }
    }

    cout << ans << '\n';

    return 0;
}

 

해당 풀이를 간편하고 천재적으로 하신 분이 있는데 감탄했다.. 참고하도록!

rebas.kr/788

BOJ 14890 · 경사로