[백준 C++] 3048 개미

이성훈·2022년 6월 24일
0

문제

개미가 일렬로 이동할 때, 가장 앞의 개미를 제외한 나머지 개미는 모두 앞에 개미가 한 마리씩 있다.

서로 반대 방향으로 이동하던 두 개미 그룹이 좁은 길에서 만났을 때, 개미는 어떻게 지나갈까?

최근 연구에 의하면 위와 같은 상황이 벌어지면 개미는 서로를 점프해서 넘어간다고 한다.

즉, 두 그룹이 만났을 때, 1초에 한번씩 개미는 서로를 뛰어 넘는다. (한 개미가 다른 개미를 뛰어 넘고, 다른 개미는 그냥 전진한다고 생각해도 된다)

하지만 모든 개미가 점프를 하는 것은 아니다. 자신의 앞에 반대 방향으로 움직이던 개미가 있는 경우에만 점프를 하게 된다.

첫 번째 그룹이 ABC로 움직이고, 두 번째 그룹의 개미가 DEF순으로 움직인다고 하자. 그럼, 좁은 길에서 만났을 때, 개미의 순서는 CBADEF가 된다. 1초가 지났을 때는 자신의 앞에 반대방향으로 움직이는 개미가 있는 개미는 A와 D다. 따라서, 개미의 순서는 CBDAEF가 된다. 2초가 되었을 때, 자신의 앞에 반대 방향으로 움직이는 개미는 B,D,A,E가 있다. 따라서, 개미의 순서는 CDBEAF가 된다.

T초가 지난 후에 개미의 순서를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 첫 번째 그룹의 개미의 수 N1과 두 번째 그룹의 개미의 수 N2가 주어진다.

다음 두 개 줄에는 첫 번째 그룹과 두 번째 그룹의 개미의 순서가 주어진다. 각 개미는 알파벳 대문자로 표현할 수 있으며, 두 그룹에서 중복되는 알파벳은 없다.

마지막 줄에는 T가 주어진다. (0 ≤ T ≤ 50)

출력

T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다.

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

풀이

문제에서 원하는 출력형식이 첫번째개미그룹의 역순 출력후,
두번째 개미그룹의 정순서를 출력하는것이다.
또, 개미의 이동방향은 변하지 않고 서로 마주보고, 스쳐가는 경우에만 스왑한다.

  1. 먼저 개미의 상태를 나타낼 자료를 만든다.
  2. 두 개미그룹을 따로 받은뒤, 하나의 그룹으로 만든다.

  3. 개미그룹을 섞는다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
struct ant {
    char alpha;
    bool dir;
};
int n1, n2; //개미그룹 수
int t; //T초
ant* group1, *group2, *list;
void print();
void logic();
void init();

void init() {
    scanf("%d%d", &n1, &n2);
    group1 = new ant[n1];
    group2 = new ant[n2];
    list = new ant[n1 + n2];
    char _;
    scanf("%c", &_); //줄바꿈문자 제거

    for (int i = 0; i < n1; i++) { //개미그룹1  아래방향 : true
        scanf("%c", &_);
        group1[i].alpha = _;
        group1[i].dir = true;
    }

    scanf("%c", &_); //줄바꿈문자 제거

    for (int i = 0; i < n2; i++) { //개미그룹2  위방향 : false
        scanf("%c", &_);
        group2[i].alpha = _;
        group2[i].dir = false;
    }
    int cur = 0;
    for (int i = n1 - 1; i >= 0; i--, cur++) {
        list[cur] = group1[i];
    }
    for (int i = 0; i < n2; i++, cur++) {
        list[cur] = group2[i];
    }


    scanf("%d", &t);
}

void logic() {
    int count = n1 + n2;
    ant _;
    while (t--) {
        for (int cur = 0; cur < count - 1; cur++) {
            //서로 스쳐가는 방향으로 마주보는경우
            if (list[cur].dir == true && list[cur + 1].dir == false) {
                _ = list[cur];
                list[cur] = list[cur + 1];
                list[cur + 1] = _;
                cur += 1;
            }
        }
    }
}

void print() {
    for (int i = 0; i < n1 + n2; i++)
        printf("%c", list[i].alpha);
}

int main(void) {
    init();
    logic();
    print();

    return 0;
}
profile
I will be a socially developer

0개의 댓글