[삼성 기출 문제] 백준 14890 경사로

문제 링크

어떻게 풀까?

이 문제의 핵심은 '경사로를 어떻게 놓으면 될까?'에 대한 결정을 하는 것입니다.

문제에경사로의 가로 길이가 2라고 하겠습니다.

땅의 상황은 위와 같다고 하겠습니다. 

아래와 같은 경우는 경사로가 설치된 곳에 중복으로 경사로를 설치했기 때문에 나타나는 문제입니다!

이 문제를 해결하기 가장 좋은 방법은 해당 좌표에 이미 경사로가 설치되었는지를 나타내는 bool 배열을 이용하는 것입니다.

해당 지점에 최초로 경사로를 만들면, 해당 자리를 true로 만듭니다. 다음에 또다시 해당 지점에 경사로를 만들려고 한다면, 경사로를 만들 수 없는 것입니다!

위의 그림을 봅시다. 위의 그림은 경사로가 지어지는 도중에 겹쳐지는 곳이 있어서 결국 경사로를 짓지 못한다는 처리를 해줘야합니다.

하지만, 경사로를 못짓는다는 표시를 한 뒤에 보라색 부분은 다시 false로 만들어줘야하죠.

이런 상황을 피하기 위해서 build를 나중에 체크합시다!

코드로 나타내면 아래와 같습니다.

bool construct(int r, int c, int d, int height)
{
    r += dy[d];
    c += dx[d];
    int sr = r, sc = c;
    for(int i = 0; i<x;i++)
    {
        if(build[r][c]) return false;
        if(map[r][c] != height || map[r][c] == -1)  return false;
        r += dy[d];
        c += dx[d];
    }
 
    r = sr; c = sc;
    for(int i = 0 ; i<x;i++)
    {
        build[r][c] = true;
        r += dy[d];
        c += dx[d];
    }
    return true;
}

위의 코드에서는 build 배열이 해당 역할을 합니다.

경사로를 짓는 방법을 완성했으니 '어떤 상황에서' 경사로를 지어야하는지에 대해서 확인해 봅시다.

위 그림에서 보면, 경사로는 왼쪽, 오른쪽을 기준으로 '높이가 1 차이날 경우'에 세우면 됩니다!

만약, 경사로의 높이 차이가 1이 나는데 경사로를 세우지 못하는 경우에는 지나갈 수 있는 길을 못만드는 것입니다.

+ 어떤 길에서 왼쪽과 오른쪽의 높이 차이가 1이 넘더라도 지나갈 수 있는 길을 만들지 못하죠!

이렇게 길의 시작부터 길의 끝을 한번 훑으면 해당 길은 지나갈 수 있는 길이 되는 것입니다!

코드로 나타내면 아래와 같습니다.

bool canBuild(int r,int c,int d)
{
    memset(build,false,sizeof(build));
 
    int prevC = c-dx[d];
    int prevR = r-dy[d];
 
    while(map[r][c] != -1)
    {
        int height = map[r][c];
        prevC = c-dx[d];
        prevR = r-dy[d];
        if(map[prevR][prevC] != -1)
        {
            if(height - 1 == map[prevR][prevC])
            {
                if(!construct(r,c,inv[d],height-1)) return false;
            }
            else if( height -1 > map[prevR][prevC])
            {
                return false;
            }
        }
        int nextC = c+dx[d];
        int nextR = r+dy[d];
 
        if(map[nextR][nextC] != -1)
        {
            if(height - 1 == map[nextR][nextC])
            {
                if(!construct(r,c,d,height-1)) return false;
                r = r+ dy[d]*x;
                c = c + dx[d]*x;
                continue;
            }
            else if( height -1 > map[nextR][nextC])
            {
                return false;
            }
        }
 
        r += dy[d];
        c += dx[d];
    }
 
    return true;
}

이제 모든 행과 열의 가로 세로를 보면서 해당 길이 지나갈 수 있는 길로 만들 수 있는지 확인해보면 됩니다!

코드

#include<iostream>
#include<cstdio>
#include<string.h>
 
using namespace std;
 
int map[102][102];
bool build[102][102];
int x;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};
const int inv[4] = {1,0,3,2};
 
bool construct(int r, int c, int d, int height)
{
    r += dy[d];
    c += dx[d];
    int sr = r, sc = c;
    for(int i = 0; i<x;i++)
    {
        if(build[r][c]) return false;
        if(map[r][c] != height || map[r][c] == -1)  return false;
        r += dy[d];
        c += dx[d];
    }
 
    r = sr; c = sc;
    for(int i = 0 ; i<x;i++)
    {
        build[r][c] = true;
        r += dy[d];
        c += dx[d];
    }
    return true;
}
bool canBuild(int r,int c,int d)
{
    memset(build,false,sizeof(build));
 
    int prevC = c-dx[d];
    int prevR = r-dy[d];
 
    while(map[r][c] != -1)
    {
        int height = map[r][c];
        prevC = c-dx[d];
        prevR = r-dy[d];
        if(map[prevR][prevC] != -1)
        {
            if(height - 1 == map[prevR][prevC])
            {
                if(!construct(r,c,inv[d],height-1)) return false;
            }
            else if( height -1 > map[prevR][prevC])
            {
                return false;
            }
        }
        int nextC = c+dx[d];
        int nextR = r+dy[d];
 
        if(map[nextR][nextC] != -1)
        {
            if(height - 1 == map[nextR][nextC])
            {
                if(!construct(r,c,d,height-1)) return false;
                r = r+ dy[d]*x;
                c = c + dx[d]*x;
                continue;
            }
            else if( height -1 > map[nextR][nextC])
            {
                return false;
            }
        }
 
        r += dy[d];
        c += dx[d];
    }
 
    return true;
}
 
int main()
{
    int t,n,input;
    memset(map,-1,sizeof(map));
    
        scanf("%d %d\n",&n,&x);
        for(int i = 1;i<=n;i++)
            for(int j = 1; j<= n; j++)
            {
                scanf("%d",&map[i][j]);
            }
        int res = 0;
        for(int i =1; i <= n; i++)
        {
            res += canBuild(1,i,1);
            res += canBuild(i,1,3);
        }
        printf("%d\n",res);
    
    return 0;
}

시간 복잡도

N 길이의 길을 2N번 씩 확인하기 때문에 시간 복잡도는 입니다.