[백준]17144 - 미세먼지 안녕! (#파이썬 #특정 루트의 순환을 구현하는 방법)

 

2차원 배열 내 수를 특정 형태에 맞게 회전시키는 로직을 for문과 while문을 적절히 활용하여야 하는 문제이다.

17144번: 미세먼지 안녕!

문제요약

숫자로 표현된 먼지들은 사방으로 퍼지며 그 크기가 퍼진 만큼 줄어든다. 또한, 숫자 -1로 표현된 공기 청정기로 먼지가 들어가면 해당 먼지는 사라지게 된다. 공기 청정기가 작동하여 먼지의 위치를 이동 시키는 특정 패턴으로 정해져 있다.

 

몇 달 전에 풀어보려고 시도하였으나 실패했었던 문제이다. 실패의 원인은 공기청정기에 의해서 먼지가 이동하는 것을 어떻게 구현해야 할지 감이 오지 않았기 때문이다. 공기청정기에 의해서 먼지가 어떻게 움직이게 되는지가 해당 문제의 핵심이라고 할 수 있다.

 

무조건 공기청정기에 의해 순환 기류가 형성된다.

문제 조건을 보면 N*M 그래프에서 공기 청정기는 항상 1 ~ N-2(인덱스 기준)에 위치하는 것을 알 수 있다. 즉, 어떻게든 위아래 공기 청정기는 순환 기류를 만들어서 먼지가 빙글빙글 돌도록 하는 것이다.

어떻게 순환 기류를 구현할 것인가?

# AS-IS
1, 2, 3
4, 5, 6
7, 8, 9

# TO-BE
2, 3, 6
1, 5, 9
4, 7, 8

해당 행렬 변환을 어떻게 쉽게 할 수 있을지 파악하는 것이 우선이다. 5를 기준으로 반시계 방향으로 회전하는 것을 구현하기 위해 아래의 절차가 필요하다.

 

1. 기준이 되는 (0, 0) 인덱스의 값을 저장한다.

2. (0, 1) 인덱스의 값을 (0, 0) 인덱스에 할당한다.

3. (0, 2) 인덱스의 값을 (0, 1) 인덱스에 할당한다.

4. (1, 2) 인덱스의 값을 (0, 2) 인덱스에 할당한다.

...

n. (1, 0) 인덱스의 값을 (2, 0) 인덱스에 할당한다.

n+1. 저장해둔 값을 (1,0)에 할당한다.

 

즉, 어떤 한 값을 저장해 두고, 저장한 값을 덮어 씌우는 방식으로 반복 수행하는 것이다. 탐색 중 이동 예정 인덱스의 값을 현재 위치한 인덱스에 할당하는 것으로도 볼 수 있다.

 

어떻게 같은 방향으로 쭉! 이동하다가 막다른 길이면 다른 방향으로 회전하여 쭉! 이동하는 것을 구현할 것인가?

위 방식대로 값은 할당할 수 있으나 탐색 중 이동 예정 위치를 문제 조건에 맞춰야 한다. 이를 위해 for 문과 while문의 중첩을 활용한다.

for 문의 역할

for 문은 탐색 이동 방향을 나타낸다. 즉, for 문에서 첫 번째 인덱스인 경우 동쪽으로, 두 번째 인덱스인 경우 남쪽으로, 세 번째 인덱스인 경우 서쪽으로, 네 번째 인덱스인 경우 북쪽으로 이동하도록 하는 것이다. 즉, 해당 for문의 인덱스 순번에 따라 이동 방향이 결정되는 것이다. 이를 코드로 나타내면 아래와 같다.

    up_dx = [-1, 0, 1, 0]
    up_dy = [0, 1, 0, -1]
    st_x, st_y = up_x, up_y
    for k in range(4):
        while True:
            prev_x, prev_y = st_x, st_y
            st_x += up_dx[k]
            st_y += up_dy[k]
            if not (0 <= st_x and st_x <= up_x and 0 <= st_y and st_y < M):
                st_x -= up_dx[k]
                st_y -= up_dy[k]
                break
            original_matrix[prev_x][prev_y] = original_matrix[st_x][st_y]

• for 문의 k는 up_dx[k]의 형태로 활용된다. k가 0인 경우 up_dx[k], up_dy[k]는 각각  -1, 0이 된다.
• k가 증가하며 st_x, st_y가 변화하는 값이 달라지는 것이다.

while 문의 역할

while 문은 범위 한계까지 '주욱!'이동하도록 하는 역할을 한다.

        while True:
            prev_x, prev_y = st_x, st_y
            st_x += up_dx[k]
            st_y += up_dy[k]
            if not (0 <= st_x and st_x <= up_x and 0 <= st_y and st_y < M):
                ...
                break

st_x, st_y는 if 문 조건을 만족하여 내부로 들어가기 전까지 지속 반복됩니다. 즉, 공기 청정기가 순회하여야 하는 범위를 모두 순회할 수 있게 된 것입니다. 종료 조건은 공기 청정기가 먼지를 순환시키는 범위를 벗어나는 경우이다.

💡 이전에 풀지 못 한 문제를 다시 풀었을 때 '맞았습니다!!'를 받으면 그 희열은 엄청나다. 도파민 💥

📁 코드 전문