3048번

문제

개미가 일렬로 이동할 때, 가장 앞의 개미를 제외한 나머지 개미는 모두 앞에 개미가 한 마리씩 있다. 서로 반대 방향으로 이동하던 두 개미 그룹이 좁은 길에서 만났을 때, 개미는 어떻게 지나갈까?

최근 연구에 의하면 위와 같은 상황이 벌어지면 개미는 서로를 점프해서 넘어간다고 한다.
즉, 두 그룹이 만났을 때, 1초에 한번씩 개미는 서로를 뛰어 넘는다. (한 개미가 다른 개미를 뛰어 넘고, 다른 개미는 그냥 전진한다고 생각해도 된다)
하지만 모든 개미가 점프를 하는 것은 아니다. 자신의 앞에 반대 방향으로 움직이던 개미가 있는 경우에만 점프를 하게 된다.

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

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

입력

첫 번째 줄에 첫 번째 그룹의 개미의 수 N1과 두 번째 그룹의 개미의 수 N2가 주어진다.
다음 두 개 줄에는 첫 번째 그룹과 두 번째 그룹의 개미의 순서가 주어진다. 각 개미는 알파벳 대문자로 표현할 수 있으며, 두 그룹에서 중복되는 알파벳은 없다.
마지막 줄에는 T가 주어진다. (0 ≤ T ≤ 50)

출력

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

문제 바로가기

백준 3048번

---

✏️분석 및 풀이

💡문제 분석

문제를 잘 읽어보면 중간에 중요한 힌트가 적혀있다.

한 개미가 다른 개미를 뛰어 넘고, 다른 개미는 그냥 전진한다고 생각해도 된다

말 그대로, 두 그룹이 있다면 하나의 그룹 값만을 이동시키면 된다는건데..
항상 문제를 어떻게 풀어야할지 모르겠다면 예시 값을 통해 풀어서 생각해보면 된다.

두 개의 그룹이 있다고 가정하자.
group1 = [1, 2, 3]
group2 = [4, 5]

T = 0
path = [3, 2, 1, 4, 5]

T = 1
path = [3, 2, 4, 1, 5]

T = 2
path = [3, 4, 2, 5, 1]

자, 이렇게 보면, 우선 우리가 해줘야할 작업들이 조금씩 보인다.
1. 하나의 리스트(path)에서 두 개의 그룹 값을 서로 구분할줄 알아야한다.
2. 같은 그룹이 연달아 있을 경우, 이동하지 않는다.

path값을 가지고 T값에 따라 계속 이 path값을 변경해가야한다.
path의 group1과 group2값이 변경되는 경우는, 특정 값과 해당 값의 다음 값이 group이 다를 경우 변경한다. 코드를 보는게 더 이해하기 쉬울것이다.

💡풀이 코드

n1, n2 = map(int, input().split())
ant1 = list(input())
ant2 = list(input())
t = int(input())

ants = ant1[::-1] + ant2
for _ in range(t):
    for i in range(len(ants)-1):
        if (ants[i] in ant1) and (ants[i+1] in ant2):
            ants[i], ants[i+1] = ants[i+1], ants[i]
            if ants[i+1] in ant1[0]:
                break
print(ants)

💡코드 분석

n1, n2엔 각 그룹의 개미 갯수를 입력받고, ant1, ant2에는 각 개미의 값을 받는다. t는 시간을 의미한다.

n1, n2 = map(int, input().split())
ant1 = list(input())
ant2 = list(input())
t = int(input())

ants는 초기 경로값을 넣는다. 위의 분석에 빗대보면 path를 의미한다.

ants = ant1[::-1] + ant2

우선 개미는 t값만큼 움직이므로, 반복횟수는 t이다.
그리고 ants값을 차례대로 검사한다. 만약 i값이 ant1그룹 내에 있는 값이면서, 그 다음 값이 다른 그룹, 즉 ant2의 값이라면 두 값을 변경한다.
그리고 ant1의 첫번째 값을 넘으면 안되기 때문에 ants[i+1]값이 ant1[0]일 경우, break하여 반복문을 벗어난다.

for _ in range(t):
    for i in range(len(ants)-1):
        if (ants[i] in ant1) and (ants[i+1] in ant2):
            ants[i], ants[i+1] = ants[i+1], ants[i]
            if ants[i+1] in ant1[0]:
                break