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

✍️ 문제 요약

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV14hwZqABsCFAYD&categoryId=AV14hwZqABsCFAYD&categoryType=CODE

SW Expert Academy

 

테이블 위에 붉은 자성체와 푸른 자성체가 있다. 자기장을 가했을 때 붉은 자성체는 S극에 이끌리고, 푸른 자성체는 N극에 이끌린다.

자기장을 가했을 때 교착 상태의 개수를 구하여라.

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

 

 

💪 무식하게 풀기

문제를 풀기 위해 간단히 정리한 조건은 아래와 같다.

- 테이블(=보드)을 90도 돌리면, 자성체가 위/아래가 아니라 좌/우로 움직이기 때문에 구현이 쉬워진다!
    - 붉은 자성체(=1) -> 왼쪽으로만 움직인다.
    - 푸른 자성체(=2) -> 오른쪽으로만 움직인다.
- 자기장을 가했을 때 "떨어뜨릴 수 있는 모든 자성체들을 떨어뜨린다"고 생각 후, 남은 자성체를 가지고 교착 상태의 수를 구하자.
- 각각의 행(가로)들을 별개로 생각하면 된다.
- 보드 위에서 "0"인 칸만 이동 가능하다. 

 

우리가 해야하는 일은 크게 두 가지가 있다.

1. 자기장을 가한 상태의 보드를 구하는 것

2. 1번 상태의 보드에서 교착 상태의 수를 구하는 것

 

개인적으로 1번보다 2번이 더 생각해야할게 많다고 느껴서 2번 코드를 따로 볼 것이다. (1번은 아래 코드 주석에 주석으로 달아놓았다.)

 

처음에는 자기장을 가한 후 붙어있는 덩어리(?)를 하나의 교착 상태로 세는 것으로 착각했다.

하지만 문제 예시를 보면, 아래 상태를 교착 상태가 7개인 상태라고 했다.

각 열에서 빨강과 파랑 즉, "12"가 붙어있을 때 하나의 교착상태로 세는 것이다.

우리는 보드를 돌렸기 때문에, 각 행에서 파랑과 빨강 즉, "21"이 붙어있을 때 교착상태로 세면 된다.

 

구현한 방법은, 보드의 각 `row`를 문자열로 변환한 뒤, 0을 기준으로 쪼개 문자열 리스트로 변환한다.

그리고 그 문자열 리스트 중에서 "21"의 개수를 카운트하여 누적하면 된다.

 # 교착상태 카운트
cnt = 0
for row in board:
    S = ''.join(map(str, row))
    for x in S.split('0'):
        cnt += x.count('21')

 

전체 코드는 아래와 같다.

import sys
sys.stdin = open("input.txt", "r")
sys.stdout = open("output.txt", "w")

# 보드 90도 회전 (size는 한 변의 길이)
def rotate(B, size):
    RB = [[0]*size for _ in range(size)]
    for i in range(size):
        for j in range(size):
            RB[j][size-1-i] = B[i][j]
    return RB

TC = 10
for test_case in range(1, TC+1):
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    board = rotate(board, N) # 90도 회전 # 이제 좌우로만 움직임 (1->왼쪽 2->오른쪽)

    for i in range(N):
        for j in range(N):
            if board[i][j] == 0: continue
            target = j
            if board[i][j] == 1: # 빨강 -> 왼쪽으로만 이동 가능
                while target-1 >= 0 and board[i][target-1] == 0:
                    board[i][target] = 0 # 기존 위치는 0으로
                    board[i][target-1] = 1 # 빨강을 왼쪽으로 이동
                    target -= 1
                if board[i][0] == 1: # 빨강이 왼쪽 끝에 온다면 떨어진다
                    board[i][0] = 0
            elif board[i][j] == 2: # 파랑 -> 오른쪽으로만 이동 가능
                while target+1 < N and board[i][target+1] == 0:
                    board[i][target] = 0 # 기존 위치는 0으로
                    board[i][target+1] = 2  # 파랑을 오른쪽으로 이동
                    target += 1
                if board[i][N-1] == 2: # 파랑이 오른쪽 끝에 온다면 떨어진다
                    board[i][N-1] = 0

    # 교착상태 카운트
    cnt = 0
    for row in board:
        S = ''.join(map(str, row))
        for x in S.split('0'):
            cnt += x.count('21')

    print('#{} {}'.format(test_case, cnt))

 

✨ 우아하게 풀기

위 풀이에서 불필요한 과정이 많음을 깨달았다..

- `flag`: 교착 상태 확인을 위한 변수

- N극을 만나면 `flag`를 활성화 시키고, 그 상태에서 S극을 만나면 교착 상태

    - 이후 `flag`를 초기화

for tc in range(1, 11):
    n = int(input())
    mag = [list(map(int, input().split())) for _ in range(n)]  # 1: N, 2: S
 
    total_res = 0
    for i in range(n):
        flag = 0
        for j in range(n):
            if mag[j][i] == 1:
                flag = 1
            elif mag[j][i] == 2:
                if flag :
                    total_res += 1
                    flag = 0
 
    print(f'#{tc} {total_res}')

 

🔗 참고

[SWEA][Python]#1220. Magnetic