[SW Expert Academy] 1220. [S/W 문제해결 기본] 5일차 - Magnetic 파이썬 정답 코드

SW Expert Academy

---

1. 문제 내용

 

 

2. 접근 방식

• 우선적으로 테이블을 가장 간단하게 구성한 다음에 교착 상태 개수를 구해야겠다고 생각했다.

 교착 상태는 테이블의 열에서 발생한다. 따라서 연산을 쉽게 하기 위해 테이블의 행과 열 위치가 바뀐 치환 행렬로 만들어야겠다고 판단했다. 이때 원소 값이 0이면 자성체가 없는 것이므로, 데이터 수를 줄이기 위해 0은 아예 제거하기로 했다.

 또한 테이블의 윗부분과 아랫부분에는 각 N극(1)과 S극(2)이 있는데, 만약 테이블 내 가장 끝단에 S극과 N극이 있다면 교착 상태 없이 이끌려 테이블 아래로 떨어진다. 즉, 가장 왼쪽에 S극(2) 성질을 갖는 자성체가, 가장 오른쪽에 N극(1) 성질을 갖는 자성체가 존재한다면 미리 제거시키면 테이블을 더욱 간단하게 구성할 수 있다.

 교착 상태는 1과 2의 덩어리이다. 만약 1 1 2 2 2 1 2 2가 있다고 하면, 1 1 2 2 2 1 2 2라는 두 덩어리로 나뉜다. 즉, 1의 개수와 2의 개수 (단 연속된 숫자는 1개로 취급)인 4의 절반이 교착 상태 개수인 것이다.

 

 

3. 정답 코드

def init() :
    n = int(input())
    data = [ ]
    for i in range(n) :
        data.append(list(map(int, input().split())))
    return n, data

def transpose_and_remove_0(data) :
    # 세로에 있는 자성체끼리만 비교하면 되기 때문에, 테이블을 전치행렬로 전환
    new_data = []
    for c in range(len(data)) :
        temp = []
        for r in range(len(data)) :
            if data[r][c] == 0 : continue
            temp.append(data[r][c])
        new_data.append(temp)
    return new_data

def remove_non_deadlock_in_end_to_end(data) :
    # 양끝에 있는 원소가 각 왼쪽이2, 오른쪽이 1이면 지우기 => 얘네는 교착 상태 없으니까
    new_data = []
    for row in data :
        for i, e in enumerate(row) : # remove 2 on left
            if e != 2 : break
        for j, e in enumerate(row[::-1]) : # remove 1 on right
            if e != 1 : break
        new_data.append(row[ i : len(row) - j ])
    return new_data

def count_deadlocks(data) :
    # 각 줄에 있는 1과 2의 개수의 절반이 교착 상태 개수 (단, 연속된 숫자는 1개로 간주 Ex: 1 1 1 => 1개 카운팅)
    count = 1
    state = 1
    for row in data :
        for e in row :
            if state != e :
                count += 1
                state = 2 if state == 1 else 1
    return count // 2

for test_case in range(1, 11):
    length, table = init()
    transposed_table = transpose_and_remove_0(table)
    reformed_table = remove_non_deadlock_in_end_to_end(transposed_table)
    
    count = count_deadlocks(reformed_table)
    print(f'#{test_case} {count}')