[SWEA] 4013. 특이한 자석(Python) / DFS

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH

SW Expert Academy

난이도가 낮은 편에 속하는 SW Expert Academy 삼성 SW 역량 테스트 모의 문제이다.

41분 소요로 워낙 많이 풀어본 문제라 오래 걸리지 않았다.

• DFS의 구조를 익힌 것이 도움이 됨
• dfs 함수 안에서 num이 3보다 작을 때와 0보다 클 때를 모두 봐야 해서 둘다 if 조건문을 걸어줘야 한다!
• 오른쪽/왼쪽 방향 살피기(자성 같거나 달라서 회전할 수 있는지 여부 확인하며 재귀로 넘기기)
• 마지막에 자석 번호별 점수를 더한 것을 출력한다.

 

파이썬 코드는 다음과 같다.

---

def dfs(num, dir):
    global check
    check[num] = 1
    if num < 3:
        if mag[num][2] != mag[num+1][6] and not check[num+1]:    # 자성 다를 경우
            dfs(num+1, -1*dir)              # 다음 자석 번호, 방향 반대
    if num > 0:
        if mag[num][6] != mag[num-1][2] and not check[num-1]:    # 자성 다를 경우
            dfs(num-1, -1*dir)              # 다음 자석 번호, 방향 반대

    if dir == 1:
        mag[num] = [mag[num].pop()] + mag[num]
    else:
        mag[num] = mag[num][1:] + [mag[num][0]]

# main
T = int(input())
for tc in range(1, T+1):
    K = int(input())
    mag = [list(map(int, input().split())) for _ in range(4)]
    for _ in range(K):      # K번 회전
        n, d = map(int, input().split())    # 자석 번호, 회전 방향
        check = [0] * 4
        dfs(n-1, d)

    result = 0
    for i in range(4):
        result += mag[i][0] * 2 ** i
    print("#{} {}".format(tc, result))

---

• 시간 : 185 ms / 메모리 : 60,448 kb
• 고찰 : DFS, BFS 문제는 함수의 구조를 익히는 것이 도움이 많이 된다. 같은 문제라도 풀 때마다 시간, 공간 복잡도를 고려하며 더욱 효율적인 코드를 짜는 힘을 기르자!