[백준/BOJ] 10813번: 공 바꾸기 (Python) 풀이

Baekjoon Online Judge (BOJ) 의 10813번 문제인 '공 바꾸기' 를 풀어보았다.
 
[문제 정보]
https://www.acmicpc.net/problem/10813

---

문제 개요:

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 바구니에는 공이 1개씩 들어있고, 처음에는 바구니에 적혀있는 번호와 같은 번호가 적힌 공이 들어있다.

도현이는 앞으로 M번 공을 바꾸려고 한다. 도현이는 공을 바꿀 바구니 2개를 선택하고, 두 바구니에 들어있는 공을 서로 교환한다.

공을 어떻게 바꿀지가 주어졌을 때, M번 공을 바꾼 이후에 각 바구니에 어떤 공이 들어있는지 구하는 프로그램을 작성하시오.

[ 입력 ]
첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에 걸쳐서 공을 교환할 방법이 주어진다. 각 방법은 두 정수 i j로 이루어져 있으며, i번 바구니와 j번 바구니에 들어있는 공을 교환한다는 뜻이다. (1 ≤ i ≤ j ≤ N)

도현이는 입력으로 주어진 순서대로 공을 교환한다.

[ 출력 ]
1번 바구니부터 N번 바구니에 들어있는 공의 번호를 공백으로 구분해 출력한다.

 

즉, N은 바구니의 번호(1~N까지)의 끝을 뜻하고, M은 공을 바꾸는 행위의 횟수(테스트 케이스의 수)를 뜻한다.

위 문제 설명처럼 i번 바구니와 j번 바구니에 들어있는 공을 교환하면 된다.

배열을 만들어서 i-1번 index의 값과 j-1번 index의 값을 서로 교환하는 식으로 문제를 풀 것이다.

 

공을 바꾸는 행위를 완료했다면 1~N번 바구니에 들어있는 공의 번호를 공백으로 구분해 출력하면 된다.

 

알고리즘:

1. N(바구니의 번호), M(공을 바꾸는 행위의 횟수, 테스트 케이스의 수)를 같은 줄에 입력받는다.
2. basket(바구니 역할을 할 배열) 변수를 만들고 빈 배열로 초기화해준다.
3. 두 바구니의 값을 서로 교환해야 하므로 값의 임시 저장소 역할을 할 tmp 변수를 만들고 0(int)으로 초기화해준다.
4. N번 반복하는 반복문을 이용해 basket에 N번 바구니까지의 바구니를 모두 넣어주고 문제에서 주어진 대로 바구니 번호와 같은 번호가 적힌 공을 넣어준다. (1부터 반복하여 0이 아닌 1부터 값이 들어가도록 해준다. 1 2 3 4 5 이런식)
5. M번 반복하는 반복문을 만들고, 공백으로 구분되어져 있는 정수 i, j를 입력받는다.
6. i번 바구니와 j번 바구니의 값을 교환하기 위하여, 먼저 j번 바구니의 공 값을 tmp 변수에 저장하고, j번 바구니에 i번 바구니의 공을 넣은 뒤, 방금 저장해 둔 j번 바구니의 공 값(tmp)을  i번 바구니에 넣어준다.
7. 공을 교환하는 작업이 완료되었다면 1~N번 바구니에 들어있는 공 번호를 공백으로 구분해 출력해야 하므로, N번 반복하는 반복문을 이용하여 basket 배열값을 모두 출력한다.

 

코드:

N, M = map(int, input().split())
basket = []
tmp = 0

for _ in range(1, N+1):
    basket.append(_)

for _ in range(0, M):
    i, j = map(int, input().split())

    tmp = basket[j-1]
    basket[j-1] = basket[i-1]
    basket[i-1] = tmp

for i in range(0, N):
    print(basket[i], end=' ')

위 풀이에 대한 질문이나 틀린 정보가 있다면 댓글로 말씀해 주시면 감사하겠습니다!