117. [삼성기출13]Python 백준 14891 번 톱니바퀴 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 14891 번 톱니바퀴 입니다.

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

14891번: 톱니바퀴

 

먼저 백준 14891 번 톱니바퀴 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

gears = [[]]
turned = [False, False, False, False, False] #이미 회전 한지
btw_same = [False, False, False, False] #같으면 true, 다르면 false

def turn(gear_num, turn_dir):
    if gear_num < 1 or gear_num > 4:
        return

    if not turned[gear_num]:
        turned[gear_num] = True

        if turn_dir == 1: #시계방향 회전
            tmp = gears[gear_num].pop(7)
            gears[gear_num].insert(0, tmp)

        else: #반시계 방향 회전
            tmp = gears[gear_num].pop(0)
            gears[gear_num].append(tmp)

        if (gear_num - 1) > 0:
            if not turned[gear_num - 1]:
                if not btw_same[gear_num - 1]:
                    turn(gear_num - 1, -turn_dir)

        if (gear_num + 1) < 5:
            if not turned[gear_num + 1]:
                if not btw_same[gear_num]:
                    turn(gear_num + 1, -turn_dir)

#build gears
for i in range(4):
    gears.append(list(map(int, input())))

#turn
K = int(input())
for _ in range(K):
    gear_num, turn_dir = map(int, input().split())
    for i in range(1, 4):
        if gears[i][2] == gears[i+1][6]:
            btw_same[i] = True
        else:
            btw_same[i] = False

    turn(gear_num, turn_dir)

    for i in range(5):
        turned[i] = False

#cal ans
score = 1
ans = 0
for i in range(1, 5):
    if gears[i][0] == 1:
        ans += score
    score *= 2

print(ans)

 

 

문제 접근

1. 매 입력마다 톱니바퀴의 상태를 저장합니다.

 

2. 톱니바퀴를 돌리는 함수를 만들어 현재 톱니 바퀴를 돌립니다.

이후 주변 톱니바퀴의 상태를 확인한 후 극이 다르고, 이미 회전하지 않았다면 재귀적으로 좌우의 톱니바퀴를

돌려줍니다. 이 때 (이미 회전한 톱니바퀴가 한번 더 돌지 않게 조심해줘야 합니다.)

 

3. 톱니바퀴는 리스트로 구현합니다.

예를들어 [1, 2, 3, 4] 4개의 톱니가 있는 바퀴를 시계방향으로 돌리면

[4, 1, 2, 3] 이 되는데, 맨 뒤의 원소를 맨 앞으로 옮기는 식으로 구현 할 수 있습니다.

[1, 2, 3, 4]를 반 시계방향으로 돌리기 위해서는 [2, 3, 4, 1] 처럼 맨 앞의 원소가 맨 뒤로 이동하면 됩니다.

 

Python 코드 구현

 

먼저 톱니바퀴를 구현하기 위한 리스트 3개를 선언합니다.

gears = [[]]
turned = [False, False, False, False, False] #이미 회전 한지
btw_same = [False, False, False, False] #같으면 true, 다르면 false

톱니바퀴가 1, 2, 3, 4 순으로 존재하므로 gears의 0번 인덱스에는 구현의 편의를 위해 더미 노드를 추가합니다.

 

turned 리스트는 밑에 구현할 톱니바퀴를 돌릴 함수 turn과 관계가 있습니다.

turn함수는 재귀적으로 좌 우의 톱니바퀴를 돌리게 되므로 불필요한 반복을 막기위해 turned 리스트를 확인하여

톱니바퀴가 이미 회전 했는지 알 수 있습니다.

마찬가지로 0번 인덱스는 더미 데이터 입니다.

 

btw_same은 1, 2, 3, 4 사이의 극이 같은지 작성하는 리스트 입니다.

톱니를 돌릴지 말지 결정하기 위해 사용합니다.

마찬가지로 0번 인덱스는 더미 데이터 입니다.

 

돌릴 톱니바퀴 번호와 돌릴 방향을 입력받습니다.

앞서 설명한 btw_same정보를 업데이트 합니다.

turn 함수를 실행합니다. turn 함수는 톱니바퀴들을 조건에 맞추어 다 돌려주는 함수입니다.

톱니바퀴를 다 돌리고 나면 turn 함수에서 사용한 turned 를 초기화 해줍니다.

for _ in range(K):
    gear_num, turn_dir = map(int, input().split())
    for i in range(1, 4):
        if gears[i][2] == gears[i+1][6]:
            btw_same[i] = True
        else:
            btw_same[i] = False

    turn(gear_num, turn_dir)

    for i in range(5):
        turned[i] = False

 

모든 톱니바퀴를 조건에 따라 다 돌리는 함수인 turn을 선언합니다.

만약 톱니바퀴의 범위를 넘어서면 종료합니다.

def turn(gear_num, turn_dir):
    if gear_num < 1 or gear_num > 4:
        return

 

현재 톱니바퀴가 이번 입력에 회전하지 않았다면 회전했다고 표시한 후

if not turned[gear_num]:
    turned[gear_num] = True

 

시계방향인지, 반시계 방향인지에 맞추어 회전합니다.

시계방향 회전은 리스트의 맨 마지막 원소를 맨 앞으로 옮겨 구현할 수 있고,

반시계방향 회전은 리스트의 맨 앞 원소를 맨 뒤로 옮겨 구현할 수 있습니다.

if turn_dir == 1: #시계방향 회전
    tmp = gears[gear_num].pop(7)
    gears[gear_num].insert(0, tmp)

else: #반시계 방향 회전
    tmp = gears[gear_num].pop(0)
    gears[gear_num].append(tmp)

 

이후 주변 톱니바퀴를 돌릴지 말지 결정하기 위해 좌우의 톱니바퀴를 탐색합니다. 

1. 양 옆의 톱니바퀴가 범위 안에 있는지 확인합니다.

2. 아직 회전하지 않았는지 확인합니다.

3. 두 톱니바퀴의 극이 다른지 확인합니다.

위의 조건들을 만족하면

turn 함수를 실행시켜 줍니다. 이때 양쪽의 톱니바퀴 번호를 넣어주고, 돌리는 방향은

현재 톱니바퀴의 반대로 돌려야 하므로 -를 곱해 입력해줍니다.

if (gear_num - 1) > 0:
    if not turned[gear_num - 1]:
        if not btw_same[gear_num - 1]:
            turn(gear_num - 1, -turn_dir)

if (gear_num + 1) < 5:
    if not turned[gear_num + 1]:
        if not btw_same[gear_num]:
            turn(gear_num + 1, -turn_dir)

 

모든 입력과 회전이 끝나면 점수를 계산해서 출력합니다.

#cal ans
score = 1
ans = 0
for i in range(1, 5):
    if gears[i][0] == 1:
        ans += score
    score *= 2

print(ans)

 

파이썬 백준 14891 번 톱니바퀴 최종 코드입니다. 

gears = [[]]
turned = [False, False, False, False, False] #이미 회전 한지
btw_same = [False, False, False, False] #같으면 true, 다르면 false

def turn(gear_num, turn_dir):
    if gear_num < 1 or gear_num > 4:
        return

    if not turned[gear_num]:
        turned[gear_num] = True

        if turn_dir == 1: #시계방향 회전
            tmp = gears[gear_num].pop(7)
            gears[gear_num].insert(0, tmp)

        else: #반시계 방향 회전
            tmp = gears[gear_num].pop(0)
            gears[gear_num].append(tmp)

        if (gear_num - 1) > 0:
            if not turned[gear_num - 1]:
                if not btw_same[gear_num - 1]:
                    turn(gear_num - 1, -turn_dir)

        if (gear_num + 1) < 5:
            if not turned[gear_num + 1]:
                if not btw_same[gear_num]:
                    turn(gear_num + 1, -turn_dir)

#build gears
for i in range(4):
    gears.append(list(map(int, input())))

#turn
K = int(input())
for _ in range(K):
    gear_num, turn_dir = map(int, input().split())
    for i in range(1, 4):
        if gears[i][2] == gears[i+1][6]:
            btw_same[i] = True
        else:
            btw_same[i] = False

    turn(gear_num, turn_dir)

    for i in range(5):
        turned[i] = False

#cal ans
score = 1
ans = 0
for i in range(1, 5):
    if gears[i][0] == 1:
        ans += score
    score *= 2

print(ans)

 

백준 14891 번  톱니바퀴 자세한 설명 및 Python 코드였습니다.

감사합니다.