입꼬리 올리고 사는 개발자

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

안녕하세요 오랜만에 오랫동안 고민한 문제가 있어 가지고 왔습니다

1. 문제

5개의 식당을 최단 거리로 방문해야 하는 문제입니다

2. 풀이

BFS와 완전탐색이 결합된 문제입니다.

BFS로 최대 20개의 식당 + 시작점 간의 모든 거리를 구해준 후(21 x 21)

DFS를 통해 모든 순서를 고려하여 최단거리를 구해주면됩니다. (순서를 고려하여 5가지를 고르는 경우의 수 -> 순열 20P5)

BFS에서 저는 기본적인 실수를 하였는데 시간이 아슬아슬한 완전탐색 문제이니 만큼

첫번째 가게에서 두번째 가게로 가는 최단 거리, 세번째 가게로 가는 최단 거리 ...를 따로따로 21x21번 구하면 시간 초과가 납니다.

한 가게를 기준으로 명확히 잡고 BFS로 구한 거리를 모든 가게에 적용시켜 주어야 합니다.

3. 코드

//https://www.acmicpc.net/problem/23817
//23817. 포항항(Gold 1, BFS, 브루트포스)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long
using namespace std;

int N, M, ans = INT_INF;
int board[1000][1000]; //입력받을 때 int로 변환해서 받기
int m_dist[1000][1000];
int r_dist[21][21]; //식당과 식당간의 거리, 0번째는 시작점으로 가정
vector<pair<int, int> > restaurant; //식당 좌표들
int rc = 0; //식당 개수 시작점은 제외
bool visited[1000][1000];
bool rvisited[21]; //식당 방문여부
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void bfs(int sr) {
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int> > q;
    q.push(make_pair(restaurant[sr].first, restaurant[sr].second));
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            m_dist[i][j] = INT_INF;
        }
    }
    visited[restaurant[sr].first][restaurant[sr].second] = 1;
    m_dist[restaurant[sr].first][restaurant[sr].second] = 0;

    while(!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(visited[nx][ny] || board[nx][ny] == -1) continue;
            //최소 거리 갱신
            m_dist[nx][ny] = m_dist[cx][cy] + 1;
            visited[nx][ny] = 1;
            q.push(make_pair(nx, ny));
        }
    }

    //한 가게를 기준으로 구한 모든 칸에 대한 최소거리를
    //식당에 관해서만 다루는 배열에 적용하기
    for(int i = 0; i <= rc; i++) {
        if(m_dist[restaurant[i].first][restaurant[i].second] == INT_INF) r_dist[sr][i] = -1;
        else r_dist[sr][i] = m_dist[restaurant[i].first][restaurant[i].second];
    }
    return;
}

void dfs(int sr, int cnt, int dist) {
    if(cnt == 5) {
        ans = (ans > dist) ? dist : ans;
        return;
    }
    
    //백트래킹 해주면서 모든 경우의 수를 탐방
    for(int i = 1; i <= rc; i++) {
        if(!rvisited[i] && r_dist[sr][i] >= 1) {
            rvisited[i] = 1;
            dfs(i, cnt + 1, dist + r_dist[sr][i]);
            rvisited[i] = 0;
        }
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    cin >> N >> M;
    char c;
    restaurant.push_back(make_pair(0, 0));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> c;
            if(c == 'X') board[i][j] = -1;
            else if(c == 'K') {
                board[i][j] = ++rc;
                restaurant.push_back(make_pair(i, j));
            }
            else if(c == 'S') {
                restaurant[0] = make_pair(i, j);
            }
        }
    }

    // SOLVE
    //한 식당을 기준으로 식당 간의 최소거리 구하기
    memset(m_dist, 0, sizeof(m_dist));
    for(int i = 0; i <= rc; i++) {
        bfs(i);
    }
    
    rvisited[0] = 1;
    dfs(0, 0, 0); //현재 가게, 들린 가게 수, 현재까지의 거리;

    //OUTPUT
    if(ans == INT_INF) ans = -1;
    cout << ans;
}

4. 이모저모

이제 BFS 정도 문제는 쉽다라고 자만한 저를 당황시킨 문제였습니다.

전체 보드도 1000 x 1000로 큰데다가 20P5라는 큰 경우의 수를 보고 완전 탐색이라고 생각하기 힘들었습니다.

난이도가 올라갈 수록 여러가지 개념이 섞인 문제(그래프 탐색에 투포인터가 섞인다던가..)가 나올텐데 더 고심해봐야겠다는 생각을 했습니다.

오늘 하루도 입꼬리 올리는 하루가 되시길 바랍니다!!

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

안녕하세요 오랜만에 포스팅 남깁니다.

이번 문제는 해결방법을 떠올리는 것은 쉽지만 구현이 많고 복잡한 부분이 있기에 Gold 2라는 난이도가 책정된 것 같습니다.

한번 보시죠!

1. 문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동하며, 가장 아래에 있는 말만 이동할 수 있다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

• A번 말이 이동하려는 칸이
  • 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
    • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
    • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
  • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
    • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.

문제가 그림과 봐야 좋을 듯 하니 링크에서 보시는 걸 추천드립니다^^

2. 풀이

풀이는 간단합니다.

체스판의 최대 크기가 12 x 12, 체스말의 최대 개수가 10, 반복횟수가 최대 1000번 이기 때문에 시간복잡도를 고려하지 않고 구현을 해주면 되겠습니다.

한 턴을 쓸 때마다 모든 체스말을 체크해주어야 하며 그 중에서도 해당 체스말이 가장 아래에 존재할 때만 이동이 가능합니다.

제가 고려한 순서는 이러한데요.1. 이동할 칸이 blue거나 체스판 밖이라면 방향 전환 후 다음 이동할 칸이 어디인지 체크 후 또 다시 blue거나 체스판 밖이라면 다음 체스말 차례로(고려할 필요가 없다면 2, 3번으로)2. 이동할 칸이 white라면 이동3. 이동할 칸이 red라면 역순으로 재정렬 후 이동4. 이동 완료 후 해당 칸의 높이가 4이상인지 확인

3. 코드

코드가 좀 길지만 함수별로 어떤 동작을 하는지 보시면 조금은 편하실 겁니다. 너저분한 코드라 죄송합니다..

//https://www.acmicpc.net/problem/17780
//17780. 새로운 게임(Gold 2, 구현)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, K, ans = 0;
int direction[11]; //체스말의 이동방향
pair<int, int> p[11]; //체스말의 위치
int color[13][13]; //체스칸의 색깔
int height[13][13]; //체스칸의 말의 높이
int sq_arr[13][13][11]; //해당 체스칸의 체스말 배열
//idx순서대로 1은 우향, 2는 좌향, 3은 북향, 4는 남향
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, 1, -1, 0, 0};
int a_flag = 0; //a_flag는 높이가 4 이상인게 생겼는지 체크,

void reverse(int x, int y) {
    if(height[x][y] <= 1) return;
    for(int i = 0; i < height[x][y] / 2; i++) {
        int tmp = sq_arr[x][y][i];
        sq_arr[x][y][i] = sq_arr[x][y][height[x][y] - 1 - i];
        sq_arr[x][y][height[x][y] - 1 - i] = tmp;
    }
}

void white(int x, int y, int nx, int ny) {
    for(int i = height[nx][ny]; i < height[nx][ny] + height[x][y]; i++) {
        //복사
        sq_arr[nx][ny][i] = sq_arr[x][y][i - height[nx][ny]];
    }
    //체스말 위치 변경 + 원래 칸 초기화 
    for(int i = 0; i < height[x][y]; i++) {
        p[sq_arr[x][y][i]].first = nx;
        p[sq_arr[x][y][i]].second = ny;
        sq_arr[x][y][i] = 0;
    }
    height[nx][ny] += height[x][y];
    height[x][y] = 0;
    if(height[nx][ny] >= 4) a_flag = 1;
}

void red(int x, int y, int nx, int ny) {
    //순서를 뒤집은 후에 그대로 옮겨주면 되므로, 본인 칸에서 순서 뒤집기 -> white()
    reverse(x, y);
    white(x, y, nx, ny);
}

void blue(int k) {
    if(direction[k] == 1) direction[k] = 2;
    else if(direction[k] == 2) direction[k] = 1;
    else if(direction[k] == 3) direction[k] = 4;
    else if(direction[k] == 4) direction[k] = 3;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    memset(height, 0, sizeof(height));
    memset(sq_arr, 0, sizeof(sq_arr));
    cin >> N >> K;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            cin >> color[i][j];
        }
    }
    //체스말의 위치와 방향 입력 후 체스칸에도 반영해주기
    for(int i = 1; i <= K; i++) {
        int tx, ty;
        cin >> tx >> ty >> direction[i];
        p[i].first = tx, p[i].second = ty;
        sq_arr[tx][ty][0] = i;
        height[tx][ty] = 1;
    }

    //SOLVE
    while(true) {
        ans++;
        //모든 말을 한번씩
        for(int i = 1; i <= K; i++) {
            int x = p[i].first;
            int y = p[i].second;
            //만약 현재 움직여야할 체스말이 가장 아래에 있는 것이 아니라면 skip
            if(sq_arr[x][y][0] != i) continue;

            int nx = x + dx[direction[i]];
            int ny = y + dy[direction[i]];

            //갈 곳이 blue 혹은 체스판 밖이라면
            if(nx < 1 || nx > N || ny < 1 || ny > N || color[nx][ny] == 2) {
                //방향 바꿔주기
                blue(i);
                nx = x + dx[direction[i]];
                ny = y + dy[direction[i]];
                //blue 바꿔준 후에도 blue가 나온 것이기 때문에 그냥 넘겨준다.
                if(nx < 1 || nx > N || ny < 1 || ny > N || color[nx][ny] == 2) {
                    continue;
                }
            }

            //갈 곳이 white라면
            if(color[nx][ny] == 0) {
                white(x, y, nx, ny);
            }
            //갈 곳이 red라면
            else if(color[nx][ny] == 1) {
                red(x, y, nx, ny);
            }

            if(a_flag) break;
        }
        //4이상이면 종료
        if(a_flag || ans > 1000) break;
    }

    //OUTPUT
    if(ans > 1000) ans = -1;
    cout << ans;
}

이런 문제는 디버깅이 오래 걸리는데 테케를 몇개를 해봐도 다 맞게 나와서 2시간이나 걸린 문제였네요.

white 함수에서 이동할 칸의 높이가 0인 경우를 괜히 구분했다가 오류잡는 데 힘들었습니다 하하

오랜만에 입꼬리가 내려갈 뻔했지만 읽으시는 분들 스마일한 하루 되시고

struct, vector를 사용하면 더 깔끔한 코드가 될 듯 하니 도전해보세용~@!