Computer Science & Engineering

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

풀이

    문제의 입력을 보면 세로선의 개수는 최대 10개, 높이는 최대 30개이다. 즉 놓치 못하는 규칙을 고려하지 않았을 때 가로선이 있을 수 있는 위치는 총 300개이다. 또 최대 3개의 가로선을 추가할 수 있는 조건을 보았을 때 브루트 포스 알고리즘으로 백트래킹을 사용해도 풀릴 수 있는 문제라고 생각하였다. 따라서 가로선이 놓일 수 있는 부분이 겹치지 않게 놓다보면 시간초과가 발생하지 않을 것이다.

    가로선은 세로선에서 오른쪽으로만 놓는다고 생각한다. 따라서 j번 세로선에 놓는다고 했을 때 j-1, j+1의 세로선에 모두 가로선이 존재하지 않아야한다. 만약 j번에 놓을 수 있을 때 dfs를 이용하여 재귀적으로 j번 세로줄부터 놓을 수 있는 위치를 다시 계산한다. 최대한 중복을 줄이기 위해 j번 세로줄부터 확인하는 것이다.

소스 코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <deque>

using namespace std;

const int MN = 9;
int N, M, H;
int ans = 4; //최대 3까지이므로 4로 설정

void dfs(int now, int n, bool ladder[31][11]) {
    if(n >= ans) return; //이미 최소값을 넘은 경우 탐색하지 않음

    bool chk = false; //모두 j번 세로줄이 j번에서 끝나는지 확인하는 변수
    for(int j = 1; j <= N; j++) {
        int now = j;
        for(int i = 1; i <= H; i++) {
            if(ladder[i][now-1]) { //왼쪽에 길이 있다면 왼쪽 세로줄로 이동
                now--;
            }
            else if(ladder[i][now]) { //오른쪽에 길이 있다면 오른쪽 세로줄로 이동
                now++;
            }
        }
        if(now != j) { //만약 j번에서 끝나지 않은 경우
            chk = true; //끝나지 않음을 체크 후 종료
            break;
        }
    }
    if(!chk)  { //만약 모두 알맞게 끝난 경우
        ans = min(ans, n); //최소값 갱신 후 더 이상 탐색하지 않음
        return;
    }

    if(n == 3) return; //3개 가로줄 사용한 경우 리턴
    for(int j = now; j < N; j++) { //지금까지 탐색한 세로줄부터
        for(int i = 1; i <= H; i++) { //모든 높이를 탐색
            if(!ladder[i][j] && !ladder[i][j+1] && !ladder[i][j-1]) { //가로줄을 놓을 수 있는 경우
                ladder[i][j] = true; //가로줄 생성
                dfs(j, n+1, ladder); //재귀
                ladder[i][j] = false; //가로줄 제거
            }
        }
    }
}

int main() {
    cin >> N >> M >> H;
    bool ladder[31][11];
    memset(ladder, 0, sizeof(ladder)); //사다리 초기화
    for(int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        ladder[a][b] = true; //가로줄 추가
    }
    dfs(1, 0, ladder); //재귀로 탐색
    if(ans == 4) cout << -1; //방법이 없는 경우 -1출력
    else cout << ans;
}

위 과정대로 작성한 코드이다. 방법이 없는 경우를 고려해 초기값을 4로 설정했다. 최대 3까지 정답이 될 수 있기 때문이다.

채점 결과

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

풀이

이 문제에서 가장 까다로웠던 것은 주사위가 굴러가는 것이다. 좌, 우로만 움직이거나 상, 하로만 움직인다면 굉장히 쉬운 일이지만 만약 지금 상태에서 상하로 구르는 것과 좌로 한 칸 이동 후에 상하로 구르는 것은 완전 다른 패턴을 가지고 있으므로 표현하는 것이 어렵다. 따라서 주사위가 상,하,좌,우로 굴렀을 때 값의 위치가 어디로 가는 지를 알고 상, 하, 좌, 우로 이동하는 함수 4개를 만들었다. 예시로 다음과 같다. 만약 주사위가 위의 문제와 같이 있고 1이 위에 있다고 가정하자. 주사위를 위로 굴렸을 때 값은 이렇게 바뀐다.

1번 자리 : 5

2번 자리 : 1

3번 자리 : 3

4번 자리 : 4

5번 자리 : 6

6번 자리 : 2

이런 방식으로 상, 하, 좌, 우로 굴렀을 때의 주사위를 나타내는 함수를 만들었다. 그 다음은 어렵지 않다. 문제에서 준 대로 바닥이 0인 경우 주사위의 아래있는 값을 복사하고 0이 아닌 경우 주사위의 면을 갱신하고 바닥을 0으로 만들면 된다.

소스 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <deque>

using namespace std;

int board[21][21];

int dice[6] = {0, 0, 0, 0, 0, 0}; //초기 주사위 전개도 순서로 초기화

void up() { //위로 굴렀을 때의 주사위 값 변화
    int tmp[6];
    tmp[0] = dice[4];
    tmp[1] = dice[0];
    tmp[2] = dice[2];
    tmp[3] = dice[3];
    tmp[4] = dice[5];
    tmp[5] = dice[1];
    memcpy(dice, tmp, sizeof(dice));
}

void down() { //아래로 굴렀을 때의 주사위 값 변화
    int tmp[6];
    tmp[0] = dice[1];
    tmp[1] = dice[5];
    tmp[2] = dice[2];
    tmp[3] = dice[3];
    tmp[4] = dice[0];
    tmp[5] = dice[4];
    memcpy(dice, tmp, sizeof(dice));
}

void left() { //왼쪽으로 굴렀을 때의 주사위 값 변화
    int tmp[6];
    tmp[0] = dice[2];
    tmp[1] = dice[1];
    tmp[2] = dice[5];
    tmp[3] = dice[0];
    tmp[4] = dice[4];
    tmp[5] = dice[3];
    memcpy(dice, tmp, sizeof(dice));
}

void right() { //오른쪽으로 굴렀을 때의 주사위 값 변화
    int tmp[6];
    tmp[0] = dice[3];
    tmp[1] = dice[1];
    tmp[2] = dice[0];
    tmp[3] = dice[5];
    tmp[4] = dice[4];
    tmp[5] = dice[2];
    memcpy(dice, tmp, sizeof(dice));
}

int main() {
    int N, M, x, y, K; cin >> N >> M >> x >> y >> K;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }
    if(board[x][y] == 0) { //바닥이 0인 경우
        board[x][y] = dice[5]; //주사위값 복사
    }
    else { //바닥이 0이 아닌 경우
        dice[5] = board[x][y]; //주사위에 바닥값 복사
        board[x][y] = 0; //바닥은 0으로
    }
    for(int i = 0; i < K; i++) {
        int a; cin >> a;
        switch(a) {
            case 1: //동쪽으로 가는 경우
                if(y + 1 < M) { //벗어나지 않을 때 동작
                    y++;
                    right();
                }
                else continue;
                break;
            case 2: //서쪽으로 가는 경우
                if(y-1 >= 0) {
                    y--;
                    left();
                }
                else continue;
                break;
            case 3: //북쪽으로 가는 경우
                if(x-1 >= 0) {
                    x--;
                    up();
                }
                else continue;
                break;
            case 4: //남쪽으로 가는 경우
                if(x+1 < N) {
                    x++;
                    down();
                }
                else continue;
                break;
        }
        if(board[x][y] == 0) { //바닥이 0인 경우
            board[x][y] = dice[5]; //바닥에 주사위 아래값 복사
        }
        else { //바닥이 1인 경우
            dice[5] = board[x][y]; //주사위 아래에 바닥값 복사
            board[x][y] = 0; //바닥은 0으로
        }
        cout << dice[0] << '\n'; //주사위 위에 있는 값 출력
    }
}

채점 결과