글 읽기 - 2020 카카오 인턴십 "경주로 건설" 문제 질문.. 7시간 고민했습니다 ㅜㅜ

nacean 3년 전 0

백준에 없는 문제를 들고 와서 죄송합니다 ㅜㅜㅜ

근데 제가 7시간동안 고민했는데 해결이 안돼서...

문제는 https://programmers.co.kr/lear...

여기에 있는 경주로 건설 문제입니다.

제 문제점은 상식적으로 목표에 도달하려면

코너를 1번이상은 돌아야하는데

n-1,n-1 인 곳에 도달했을때 코너를 0번 돌고 도달한 것이 있습니다.

ex) 4번째 테스트케이스에서 S[6][6][0]~ 에서 값이 들어가있었습니다.

코너를 도는 코드에서는 무조건 corner+1을 해줬는데

어째서 corner == 0 인 값이 마지막에 나오는지 모르겠습니다 ㅜㅜㅜ...

진짜 이거 해결 못하면 잠 못잘꺼같습니다 ㅜㅜㅜ

답변해주시면 감사하겠습니다!!

#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <iostream>
using namespace std;
int dx[4] = {1,0,-1,0}; // 우:0, 상:1, 좌:2, 하:3   0<->2 1<->3
int dy[4] = {0,1,0,-1};

int S[25][25][25][4]; // y좌표,x좌표,코너갯수,방향 = 직선거리
bool visit[25][25][25][4];


int solution(vector<vector<int>> board) {
    int answer = 999999999;
    int n = board.size();
    queue<pair<pair<int,int>,pair<int,int>>> q; // y좌표,x좌표,코너갯수,방향
    
    for(int i=0;i<25;i++) //직선거리를 최대로 초기화
        for(int j=0;j<25;j++)
            for(int k=0;k<25;k++)
                for(int t=0;t<4;t++)
                    S[i][j][k][t] = 9999;
    
    if(board[0][1] == 0) //오른쪽으로 이동
    {
        q.push(make_pair(make_pair(0,1),make_pair(0,1)));
        S[0][1][0][1] = 1;
        visit[0][1][0][1] = true;
    }
    if(board[1][0] == 0) //아래로 이동
    {
        q.push(make_pair(make_pair(1,0),make_pair(0,0)));
        S[1][0][0][0] = 1;
        visit[1][0][0][0] = true;
    }
    while(!q.empty())
    {
        int now_y = q.front().first.first;
        int now_x = q.front().first.second;
        int now_corner = q.front().second.first; //지금껏 코너 수
        int now_swift = q.front().second.second; //지금 바라보는 방향
        q.pop();
        
        for(int i=0;i<4;i++)
        {
            if(now_swift != i && ((i%2 == now_swift % 2))) //뒤로 돌아가는건 안됌
                continue;
            
            int next_x = now_x+dx[i]; //다음 x좌표
            int next_y = now_y+dy[i]; //다음 y좌표
            
            if(next_x >=0 && next_x < n && next_y >=0 && next_y < n) //경계를 안 벗어났을때
            {
                if(board[next_y][next_x] == 1) //벽이라면 안함
                    continue;
                
                else if(now_swift == i) // now->next가 직진임 : 코너없고 거리만 +
                {
                    if(visit[next_y][next_x][now_corner][i] == false)
                    {
                    q.push(make_pair(make_pair(next_y,next_x),make_pair(now_corner,i)));
                    S[next_y][next_x][now_corner][i] = S[now_y][now_x][now_corner][now_swift] + 1;
                    visit[next_y][next_x][now_corner][i]=true;
                    }
                }
                else // now->next 가 코너링
                {
                    if(now_corner < n*n && visit[next_y][next_x][now_corner+1][i] ==false) // 코너링 초과는 안됌 : 코너+, 거리+
                    {
                        q.push(make_pair(make_pair(next_y,next_x),make_pair(now_corner+1,i)));
                        S[next_y][next_x][now_corner+1][i] = S[now_y][now_x][now_corner][now_swift] + 1;
                        visit[next_y][next_x][now_corner+1][i]=true;
                    }
                }   
            }
        }
    }
    for(int i=0;i<2;i++) //도착할때는 오른쪽방향이거나 아래방향일때 밖에 없음
    {
        for(int j = 0; j< n*n; j++)
        {
            answer = min(answer, (j*500) + (S[n-1][n-1][j][i] * 100));
        }
    }
               
    return answer;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2020 카카오 인턴십 "경주로 건설" 문제 질문.. 7시간 고민했습니다 ㅜㅜ

nacean 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말