[Python] Magmetic (SWEA 1220번 파이썬)

테이블 위에 자성체들이 놓여 있다.

자성체들은 성질에 따라 색이 부여되는데, 푸른 자성체의 경우 N극에 이끌리는 성질을 가지고 있고, 붉은 자성체의 경우 S극에 이끌리는 성질이 있다.

아래와 같은 테이블에서 일정 간격을 두고 강한 자기장을 걸었을 때, 시간이 흐른 뒤에 자성체들이 서로 충돌하여 테이블 위에 남아있는 교착 상태의 개수를 구하라.

아래는 자성체들이 놓여 있는 테이블을 위에서 바라본 모습이다.
 

 
A로 표시된 붉은 자성체의 경우 S극에 이끌리면서 테이블 아래로 떨어지게 된다.

B로 표시된 푸른 자성체의 경우 N극에 이끌리면서 테이블 아래로 떨어지게 된다.

나머지 자성체들은 서로 충돌하며, 교착 상태에 빠져 움직이지 않게 된다.

D로 표시된 자성체들에서 알 수 있듯 한 쪽 방향으로 움직이는 자성체의 개수가 많더라도 반대 방향으로 움직이는 자성체가 하나라도 있으면 교착 상태에 빠져 움직이지 않는다.

D로 표시된 자성체들과 같이 셋 이상의 자성체들이 서로 충돌하여 붙어 있을 경우에도 하나의 교착 상태로 본다.

C와 D는 좌우로 인접하여 있으나 각각 다른 교착 상태로 판단하여 2개의 교착 상태로 본다.

E의 경우와 같이 한 줄에 두 개 이상의 교착 상태가 발생할 수도 있다.

F의 경우 각각 다른 교착상태로 판단하여 2개의 교착상태로 본다.

위의 예시의 경우 테이블 위에 남아있는 교착상태는 7개이므로 7를 반환한다.


[제약 사항]

자성체는 테이블 앞뒤 쪽에 있는 N극 또는 S극에만 반응하며 자성체끼리는 전혀 반응하지 않는다.

테이블의 크기는 100x100으로 주어진다. (예시에서는 설명을 위해 7x7로 주어졌음에 유의)

[입력]

10개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 정사각형 테이블의 한 변의 길이가 주어진다. (이 값은 항상 100이다)

그 다음 줄부터 100 x 100크기의 테이블의 초기 모습이 주어진다. 1은 N극 성질을 가지는 자성체를 2는 S극 성질을 가지는 자성체를 의미하며 테이블의 윗부분에 N극이 아래부분에 S극이 위치한다고 가정한다.

(N극 성질을 가지는 자성체는 S극에 이끌리는 성질이 있다.)

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 교착 상태의 개수를 출력한다.

 

 

 

해결하는데 정말 오래 걸린 문제입니다...

 

기본적으로 주어지는 2차원 배열을 전치행렬로 만들 경우 상/하 이동을 좌/우 이동으로 구현할 수 있습니다.(큐 자료구조)

 

빨간 자석인 1은 오른쪽(S극)으로 끌리고, 파란 자석인 2는 왼쪽(N극)으로 끌리게 됩니다.

따라서 행에서 행의 가장 앞자리에 있는 2는 모두 제거하고, 가장 뒤에 있는 1도 모두 제거해야 합니다.(극에 끌려 밑으로 떨어짐)

이렇게 되면 교착상태인 자석들만 남아있게 됩니다.

 

이후 교착상태에 있는 1과 2를 제거합니다.

스택 자료구조를 사용해서 제거하며, 1을 기준으로 짝을 맞춰서 제거합니다.(스택 괄호 문제와 비슷하게 접근)

행에서 1일 경우 스택에 넣고, 2일 경우 스택을 초기화하고 교착상태의 갯수에 +1을 합니다.

이때, 중요한 것은 1과 2가 짝이 되어야 하기 때문에 2일 경우에 stack이 존재한다(1이 있음)라는 조건이 있어야 합니다.

 

 

코드

#SWEA 1220 Magnetic
from collections import deque

for t in range(10):
    answer = 0
    n = int(input()) 
    graph = [[] for _ in range(100)] #2차원 배열을 입력받아서 0 제거 후 전치행렬 변환
    for i in range(100):
        arr = list(map(int, input().split()))
        for j in range(100):
            if arr[j] == 2:
                graph[j].append(2)
            elif arr[j] == 1:
                graph[j].append(1)

    new_graph = []
    for i in range(100):
        q = deque(graph[i])
        while True: #1은 오른쪽으로, 2은 왼쪽으로 끌림
            if q[-1] == 1: #배열 오른쪽에 1이 있으면 전부 제거
                q.pop()
            if q[0] == 2: #배열 왼쪽에 2이 있으면 전부 제거
                q.popleft()
            if q[0]==1 and q[-1]==2: #더이상 문제 없으면 종료
                new_graph.append(list(q))
                break

    for i in range(100): #1과 2를 짝 맞춰서 제거하기 ( 1을 기준으로 )
        stack = [1] #배열의 시작은 무조건 1임
        for j in range(1,len(new_graph[i])):
            #스택에는 1만 쌓으면 됨(이진 분류). 현재값이 1이면 append / 현재값이 2면 스택비우기
            if new_graph[i][j] == 1:
                stack.append(1)
            elif stack and new_graph[i][j] == 2:
                stack = []
                answer += 1

    print(f"#{t+1}", answer)