[python] 백준 3048번 : 개미

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

3048번: 개미

[구현]

n1, n2 = map(int, input().split())
ant1 = list(input())
ant2 = list(input())
path = ant1[::-1] + ant2
t = int(input())
for _ in range(t):
    for i in range(len(path)-1):
        # 두 개미 그룹이 만났다면 자리를 바꾼다.
        if path[i] in ant1 and path[i+1] in ant2:
            path[i], path[i+1] = path[i+1], path[i]
            # 위치를 바꾼 개미가 선두 개미면 반복을 멈춘다. 
            if path[i+1] == ant1[0]:
                break
print(''.join(path))

            if path[i+1] == ant1[0]:
                break 

이 조건문이 왜 필요한지 잘 이해가 가지 않았는데 아래와 같은 명확한 반례가 있었다. 

 

3 4
QIY
GMVZ

1

 

이 케이스의 정답은 YIGQMVZ지만, 조건문이 없다면 YIGMVZQ를 반환한다.

 

조건문이 없을 때 동작하는 방식을 그림으로 나타내봤다.

 

t = 1일때, 내부 for문은 두 그룹 개미를 합친 path길이 만큼 반복된다.

1초일 때 G와 Q는 서로 마주보게 되고 두자리를 바꾸고 종료해야 한다. 

 

하지만 이때 선두개미에서 조건을 종료(if path[i+1] == ant1[0])해주지 않으면

swap된 이후의 자리와 오른쪽 자리가 또다시 if문 조건(if path[i] in ant1 and path[i+1] in ant2:)을 만족하게 되고

계속해서 자리를 뒤바꾸게 된다. 그래서 결국 Q가 맨 끝에 위치하게 되는 것이다. 

 

따라서 왼쪽 개미군단(ant1)의 선두개미가 오른쪽 개미군단(ant2)과 마주 보게 되어 swap한다면 break문을 걸어야 한다.