[SWEA|파이썬] 1220. [S/W 문제해결 기본] 5일차 - Magnetic (D3)

문제

https://tinyurl.com/2jsfjmya

SW Expert Academy

 

 

💡문제풀이 아이디어

테이블 상단이 N극, 하단이 S극이므로 교착상태의 형태는

N극 (1)

S극 (2)

이다.

👉 이런 형태를 하고 있는 자석들의 갯수를 세면 교착상태의 갯수를 알 수 있다.

 

❓이유

👉 N극은 테이블 하단 S극의 영향을 받아 아래로 내려가고 싶어하는데 위쪽으로 올라가려는 S극이 아래에 걸려 움직일 수 없다.

👉 마찬가지로 S극 역시 테이블 상단으로 움직이고 싶어하지만 아래로 내려가려고 하는 N극이 위에 걸려 있기 때문에 움직일 수 없다.

 

 

🐍파이썬

스택을 이용한 풀이

T = 10
for test_case in range(1, T + 1):
    table = int(input())
    mgt = [list(map(int, input().split())) for _ in range(100)]
    cnt = 0
    #열 순회
    for c in range(table):
        stack = []
        for r in range(table):
            if not stack and mgt[r][c] == 1:	#스택이 비어있고 N극(빨간색, 1)인 경우
                stack.append(1)	#1넣기
            elif stack and mgt[r][c] == 2:	#스택에 1이 들어있고 S극(파란색, 2)인 경우
                cnt += stack.pop()	#교착상태  check
    print("#{} {}".format(test_case, cnt))

한 열에서, 스택에 1(N극)이 들어있는 상태에서 자석 2(S극)이 존재한다면 무조건 교착상태가 된다.

 

❓이유

N극 (1) --- 스택에 들어있음

S극 (2) --- mgt[r][c]

형태가 위에 명시한 교착상태의 자석 형태와 동일하다.

따라서 이미 들어있던 1을 빼내어 answer에 더해 교착상태의 갯수를 카운팅한다.

---

플래그를 이용한 풀이

T = 10
for test_case in range(1, T + 1):
    _ = int(input())
    arr = []
    ans = 0
    
    for _ in range(100):
        arr.append(list(map(int, input().split())))
        
    for i in range(100):
        n_flag = 0
        s_flag = 0
        for j in range(100):
            if arr[j][i] == 1:
                n_flag = 1
                s_flag = 0
            elif arr[j][i] == 2:
                s_flag = 1
                n_flag = 0
            if arr[j][i] == 0:
                if n_flag == 1:
                    arr[j][i] = 1
                elif s_flag == 1:
                    arr[j][i] = 2
                    
    for i in range(100):
        for j in range(99):
            if arr[j][i] == 1 and arr[j+1][i] == 2:
                ans += 1
                
    print("#{} {}".format(test_case, ans))

각 열을 순회하며 arr[j][i]가 1(N극)인 경우 n_flag를 1로 만들고 s_flag를 0으로 만든다.

마찬가지로 arr[j][i]가 2(S극)인 경우 s_flag를 1로 만들고 n_flag를 0으로 만든다.

값이 0인 원소를 만나면 켜져있는 플래그 대로 0또는 1로 원소값을 대체한다. 👉 자성에 따라 밀려난 자석들 표현

 

두번째 for문에서는, 한 열에서 현재 행의 원소값이 1(N극)이고 다음 행의 원소값이 2(S극)인 경우만의 갯수를 세어 교착상태의 갯수를 카운팅한다. 

N극 (1)

S극 (2)