[DFS] 백준#14891: 톱니바퀴/Python

📝 문제

https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

💡 접근법

DFS 알고리즘을 활용하여 문제를 해결하였습니다. 문제 풀이는 다음과 같이 크게 세 부분으로 나눌 수 있습니다.

• 첫째, 톱니바퀴를 시계 혹은 반시계 방향으로 회전시키는 함수
• 둘째, DFS 알고리즘을 활용하여 인접한 톱니바퀴의 회전 여부를 탐색하는 함수
• 셋째, \(K\)번의 회전 후에 최종적으로 점수를 계산하는 함수

특정 번호의 톱니바퀴에서 좌측과 우측에 인접한 톱니바퀴도 연쇄적으로 회전시킬 수 있는지 확인하기 위해 재귀 함수를 활용한 DFS를 사용하였습니다.

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline

def rotate_clockwise(graph):
    temp = graph[7]
    for i in range(6, -1, -1):
        graph[i+1] = graph[i]
    graph[0] = temp

def rotate_counterclockwise(graph):
    temp = graph[0]
    for i in range(7):
        graph[i] = graph[i + 1]
    graph[7] = temp

def dfs(i, rotate):
    global visited
    if not visited[i]:
        visited[i] = True
        left = graph[i][6]
        right = graph[i][2]
        if rotate == 1:
            rotate_clockwise(graph[i])
        else:
            rotate_counterclockwise(graph[i])
        # 좌측에 톱니바퀴의 존재여부와 인접한 톱니 간 다른 극인지 확인
        if 1 <= i-1 and left != graph[i-1][2]:
            # 좌측 톱니바퀴를 현재 회전한 방향과 반대 방향으로 회전
            dfs(i - 1, -rotate)
        # 우측 톱니바퀴의 존재여부와 인접한 톱니 간 다른 극인지 확인
        if i+1 <= 4 and right != graph[i+1][6]:
            # 우측 톱니바퀴를 현재 회전한 방향과 반대 방향으로 회전
            dfs(i + 1, -rotate)

def score():
    answer = 0
    for i in range(1, 5):
        if graph[i][0] == '1':
            answer += 2**(i-1)
    return answer

if __name__ == '__main__':
    graph = [[]]
    for _ in range(4):
        graph.append(list(input().rstrip()))

    K = int(input())
    for _ in range(K):
        i, rotate = map(int, input().split())
        visited = [False]*5
        dfs(i, rotate)

    answer = score()
    print(answer)

2) 해설

(1) 패키지 import

import sys; input = sys.stdin.readline

파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.

(2) DFS 알고리즘

def dfs(i, rotate):
    global visited
    if not visited[i]:
        visited[i] = True
        left = graph[i][6]
        right = graph[i][2]
        if rotate == 1:
            rotate_clockwise(graph[i])
        else:
            rotate_counterclockwise(graph[i])
        # 좌측에 톱니바퀴의 존재여부와 인접한 톱니 간 다른 극인지 확인
        if 1 <= i-1 and left != graph[i-1][2]:
            # 좌측 톱니바퀴를 현재 회전한 방향과 반대 방향으로 회전
            dfs(i - 1, -rotate)
        # 우측 톱니바퀴의 존재여부와 인접한 톱니 간 다른 극인지 확인
        if i+1 <= 4 and right != graph[i+1][6]:
            # 우측 톱니바퀴를 현재 회전한 방향과 반대 방향으로 회전
            dfs(i + 1, -rotate)

• 2~4번째 라인
  • 회전 가능여부를 탐색한 톱니바퀴를 재탐색하는 것을 방지하기 위해 방문 여부 관리
• 5~6번째 라인
  • 다른 톱니바퀴들과 인접하게 되는 톱니바퀴의 좌측과 우측 끝 부분
• 7~10번째 라인
  • 해당 톱니바퀴를 시계 혹은 반시계 방향으로 회전하는 함수 호출
• 12~19번째 라인
  • 회전한 톱니바퀴의 좌측과 우측에 톱니바퀴가 있는지 확인하고, 있다면 인접한 톱니가 반대 전극을 가지는지 확인
  • 위 조건을 만족한다면 재귀적으로 DFS 함수를 호출하여 해당 톱니바퀴를 회전

(3) Move 함수

def rotate_clockwise(graph):
    temp = graph[7]
    for i in range(6, -1, -1):
        graph[i+1] = graph[i]
    graph[0] = temp

def rotate_counterclockwise(graph):
    temp = graph[0]
    for i in range(7):
        graph[i] = graph[i + 1]
    graph[7] = temp

톱니바퀴를 회전시키는 함수입니다. 회전하는 방향에 따라 인덱스를 \(1\)씩 변화시키며 값을 교환합니다.

(4) 합산 함수

def score():
    answer = 0
    for i in range(1, 5):
        if graph[i][0] == '1':
            answer += 2**(i-1)
    return answer

모든 회전이 끝났다면 문제에서 주어진 조건에 맞게 점수를 합산합니다.

(5) 메인함수

if __name__ == '__main__':
    graph = [[]]
    for _ in range(4):
        graph.append(list(input().rstrip()))

    K = int(input())
    for _ in range(K):
        i, rotate = map(int, input().split())
        visited = [False]*5
        dfs(i, rotate)

    answer = score()
    print(answer)

메인 함수입니다. 톱니바퀴별 전극 정보를 저장하는 리스트(graph)는 [0] 인덱스에 빈 리스트를 넣어 톱니바퀴 개수보다 \(1\)개 많게 세팅하였습니다. 이는 문제에서 톱니바퀴 번호가 \(1\)부터 시작하기 때문에, 리스트에서 인덱싱할 때 톱니바퀴 번호로 직관적으로 사용하기 위함입니다.

✅ 채점 결과

채점 결과

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_14891.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

📚 참고할 만한 포스팅

문제 풀이에 사용한 DFS 알고리즘에 대한 자세한 설명은 아래 포스팅을 참고해 주세요.

https://heytech.tistory.com/55

[알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.