[Python] 1220번 [S/W 문제해결 기본] 5일차 - Magnetic

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14hwZqABsCFAYD

---

 

25/07/28

 

 

아이디어를 떠올리면 쉽게 구현할 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

일단 문제를 보면 열 별로 독립이기 때문에, 하나의 열에 대해서만 어떻게 움직일지를 생각해보자.

 

구현의 편의 상 열 별로 구현하기가 힘드므로, list(map(list, zip(*M)))을 통해 전치 행렬을 취해줌으로써 행 별로 순회하도록 고쳐보자.

 

교착상태가 되려면 빨간 색이 나온 후에 파란 색이 나와야 한다.

 

따라서, 빨간색이 나올 때 flag를 세워주고, 교착상태가 있다면 답에 더해준다.

 

빨간색이 나온 뒤에 파란색이 나온 다면, 즉, flag와 파란색이 동시에 있다면 교착상태가 생긴 것이므로 교착상태가 하나 있다는 표시를 해준다. 그리고 빨간색과 파란색은 서로 교착상태 한 쌍을 이루므로, flag를 다시 False로 만든다.

 

이런식으로 For문을 순회한 다음, 마지막에 남아있는 교착상태가 있다면 그 값을 답에 더해주면 된다.

 

시간 복잡도는 $\mathcal{O}(TN^{2})$이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

def solve(test_case_num):
    N = int(input())
    M = [list(map(int, input().split())) for _ in range(N)]
    M_t = list(map(list, zip(*M))) # Transpose
    ans = 0
    for row in M_t: # 행마다 독립이므로 행마다 세어줌
        flag = False # 교착상태가 되려면 빨간색이 나온 후에 파란색이 나와야 한다.
        cnt = 0
        for ele in row:
            if ele == 1: # 빨간색이 나오면
                flag = True 
                ans += cnt
                cnt = 0
            elif ele == 2 and flag: # 빨간색이 나오고 파란색이 나오면
                cnt = 1
                flag = False
        if cnt > 0: # 빨간색이 나올 때 1씩 더했으므로, 만약 cnt가 1이라면 이전 교착상태가 하나 남아있는거임
            ans += cnt
    print(f'#{test_case_num} {ans}')
    return

def main():
    T = 10
    for i in range(1, T + 1):
        solve(i)

main()