[백준]14891 톱니바퀴 - 골드 5

 

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• 구현, queue 자료구조 

---

1. 문제설명

 

쉽게말해 톱니바퀴가 4개있고 톱니는 8개씩 달려있습니다.

 

이 톱니와 맞물리는 톱니가 서로 상극인 경우 회전 방향에 따라 같이 회전합니다.

 

예를들어 1번 톱니와 맞물리는 2번 톱니가 서로 상극인경우

 

1번 톱니바퀴가 시계방향으로 회전하면 2번 톱니바퀴는 반시계방향으로 회전합니다.

 

더 쉽게 생각하면 위 그림에서 손가락을 이용해 톱니를 회전시키는 경우 1번은 오른쪽으로 돌아가고 2번은 왼쪽으로 돌아갑니다.

 

이를 통해 톱니의 상태가 주어지고 어떤 톱니바퀴를 어떻게 회전시킬지 주어질 때 마지막까지 회전을 종료하고 톱니의 12시에 있는 극성이 S극이면 그 점수를 모두 더해 출력하는 프로그램을 작성하는 것입니다.

---

[제한사항]

• 시간 제한 2초
• 메모리 제한 512MB
• N극은 0, S극은 1
• 1 ≤ K ≤ 100
• 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.
• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

---

2. 접근방식

 

우선 톱니회전에 관해 한가지 주의점이 있습니다.

 

바로 지정된 톱니의 회전에 따라 다른 톱니도 영향을 받습니다

 

예를 들어 1번이 2번과 맞물리고 2번이 3번과도 맞물린다고 할때

1번을 시계방향으로 회전하면

2번은 반시계방향으로 회전하고

3번은 시계방향으로 회전합니다.

 

이렇게 회전시킬 톱니를 기준으로 회전이 가능한 모든 경우를 찾고

회전 방향에 따라서 주어진 톱니를 회전시키면 될 것 같습니다.

 

주어지는 톱니는 12시 방향부터 시계방향으로 주어진다고 했습니다.

 

여기서 톱니가 맞물리는 경우는

1번 톱니바퀴의 2번째 톱니와

2번 톱니바퀴의 6번째 톱니가 서로 맞물리고

 

2번 톱니바퀴의 2번째 톱니와

3번 톱니바퀴의 6번째 톱니가 서로 맞물리고

 

3번 톱니바퀴의 2번째 톱니와

4번 톱니바퀴의 6번째 톱니가 서로 맞물립니다.

 

즉 주어진 톱니의 정보의 2번과 6번 정보에 따라서 톱니가 회전할지, 회전하지 않을지 정해지는 것입니다.

 

톱니가 회전하는 경우

 

시계방향으로 회전하면 가장 마지막 톱니가 12시에 위치합니다.

즉 배열의 마지막 인자가 가장 처음으로 들어오는 것이고

 

반시계방향으로 회전하면 2번째 톱니가 12시에 위치합니다.

이는 배열의 첫번째 인자가 가장 마지막에 오는 것입니다.

 

이를 구현하려면 queue 자료구조를 활용해 pop, popleft, append, appendleft를 활용하면 될 것 같습니다.

---

3. 코드

import sys
input = sys.stdin.readline
from collections import deque

N = 4
wheels = [''] + [deque(map(int, input().strip())) for _ in range(4)]
K = int(input())

for _ in range(K):
    info, dir = map(int, input().split())

    # 회전후보 구하기
    rotation = [(info, dir)]

    # 현재 톱니 기준 오른쪽 톱니 확인
    tmp_dir = dir
    for i in range(info+1, N+1):
        if wheels[i-1][2] != wheels[i][6]:
            tmp_dir *= -1
            rotation.append((i, tmp_dir))
        else:
            break

    # 현재 톱니 기준 왼쪽 톱니 확인
    tmp_dir = dir
    for i in range(info-1, 0, -1):
        if wheels[i][2] != wheels[i+1][6]:
            tmp_dir *= -1
            rotation.append((i, tmp_dir))
        else:
            break

    # 회전 적용
    for i, d in rotation:
        # 시계방향 회전
        if d == 1:
            wheels[i].appendleft(wheels[i].pop())
        # 반시계 방향 회전
        else:
            wheels[i].append(wheels[i].popleft())

# 점수 계산
answer = 0
for i in range(1, 5):
    if wheels[i][0] == 1:
        answer += (1 << (i - 1))    # 비트시프트 이용해서 점수 쉽게 계산

print(answer)

.

---

[코드설명]

N = 4
wheels = [''] + [deque(map(int, input().strip())) for _ in range(4)]
K = int(input())

for _ in range(K):
    info, dir = map(int, input().split())

 

입력을 받고 K번 톱니를 회전시키기 위해서 반복문을 활용하였습니다.

 

여기서 톱니의 정보는 1번부터 주어지기 때문에 이를 맞춰주기 위해 wheels 배열에 의미없는 공백 배열을 추가해 주었는데

 

여기서 공백 배열 대신 0을 추가하면 TypeError: 'int' object is not subscriptable 라는 에러가 발생할 수 있습니다.

 

이는 배열의 첫번째 인자가 int 타입이라 발생하는 에러이므로 None, '', False, True 등 의미없는 값을 넣어주면 됩니다.

 

또 queue 자료구조를 활용하기 위해 입력받는 정보를 deque에 저장해 주었고, 2차원 배열 형식으로 만들어 주었습니다.

 

톱니는 총 4개가 주어지니 N은 4로 선언해 주었습니다.

---

# 회전후보 구하기
    rotation = [(info, dir)]

    # 현재 톱니 기준 오른쪽 톱니 확인
    tmp_dir = dir
    for i in range(info+1, N+1):
        if wheels[i-1][2] != wheels[i][6]:
            tmp_dir *= -1
            rotation.append((i, tmp_dir))
        else:
            break

    # 현재 톱니 기준 왼쪽 톱니 확인
    tmp_dir = dir
    for i in range(info-1, 0, -1):
        if wheels[i][2] != wheels[i+1][6]:
            tmp_dir *= -1
            rotation.append((i, tmp_dir))
        else:
            break

 

우선 현재 톱니바퀴 번호는 회전시킬 것이니 회전 후보에 현재의 톱니바퀴 번호와 회전 방향을 저장해 줍니다.

 

주어진 현재 톱니바퀴를 기준으로 오른쪽 톱니바퀴와 왼쪽 톱니바퀴가 회전이 가능한지 파악해 주어야 합니다.

 

따라서 반복문 for를 이용해 현재 톱니바퀴 기준 오른쪽 톱니바퀴를 검사합니다.

 

탐색의 위치는 현재 톱니바퀴 다음번호를 찾아야 하니 입력받은 info + 1 을 해주었고, 마지막까지 탐색하기 위해 N + 1을 해주었습니다.

 

오른쪽 톱니가 맞물리는 경우는 현재 톱니바퀴의 2번째 톱니와 오른쪽 톱니바퀴의 6번 톱니가 서로 상극인 경우 입니다.

 

이 경우를 찾아 회전방향을 저장해 주었고

 

서로 같은 극이 오는 경우 더이상 탐색할 필요가 없으니 break 해주었습니다.

 

동일하게 왼쪽 톱니바퀴의 경우도

 

현재 톱니의 6번째 톱니와 왼쪽 톱니의 2번째 톱니가 서로 상극인 경우를 찾아주면 됩니다.

 

회전의 경우 현재 톱니바퀴가 회전방향과 반대방향으로 회전하니 이를 맞춰주기 위해 tmp_dir을 구해주었고 이를 저장해 주었습니다.

---

    # 회전 적용
    for i, d in rotation:
        # 시계방향 회전
        if d == 1:
            wheels[i].appendleft(wheels[i].pop())
        # 반시계 방향 회전
        else:
            wheels[i].append(wheels[i].popleft())

# 점수 계산
answer = 0
for i in range(1, 5):
    if wheels[i][0] == 1:
        answer += (1 << (i - 1))    # 비트시프트 이용해서 점수 쉽게 계산

print(answer)

 

모든 회전 후보를 다 구했으니 queue를 회전해 주면 됩니다.

 

시계방향인 경우 가장 마지막 인자가 가장 처음으로 와야하니 appendleft를 활용하였고

 

반시계방향의 경우 가장 처음 인지가 가장 마지막에 와야하니 popleft를 활용하였습니다.

 

그 후 K번 반복이 종료되면 점수를 계산하는데

점수는 주어진 톱니바퀴의 번호의 12시방향 즉 가장 첫번째 톱니가 1이면 점수를 얻습니다.

 

1번이 1이면 1점

2번이 1이면 2점

3번이 1이면 4점

4번이 1이면 8점 이런식으로 점수가 배로 늘어나니 비트시프트 연산을 이용해 주어진 번호를 왼쪽으로 시프트 연산을 실시하면

 

동일한 결과를 얻을 수 있습니다.

 

이렇게 answer 구했고 출력해 주었습니다.

---

4. 결과

---

[회고]

 

처음에 문제를 보고 쉽네 그냥 그 번호와 맞물리는 주변 톱니만 회전하면 되는거 아닌가? 했는데 다른 경우도 존재하는 것을 보고 고민이 길어졌습니다.

 

주어진 톱니가 4개 뿐이라 하드코딩을 실시할까도 했지만 일반화를 시키고 싶어서 그렇게 하진 않았습니다.

 

다만 하드코딩의 경우를 생각하며 문제의 조건에 알맞는 조건을 설정할 수 있었고, 코드를 작성할 수 있었습니다.

 

또한 점수계산도 동일한 코드를 여러번 반복하는게 불필요해 보였고 좋은 방법을 찾던 중 시프트연산 쓸 수 있나 싶어서 구글 검색으로 찾아봤고

 

제가 원하는 결과를 출력할 수 있어서 비트시프트 연산을 이용했습니다.

 

이번 문제의 경우 현재 톱니를 기준으로 왼쪽 톱니와 오른쪽 톱니를 구분하는게 가장 힘들었는데,

 

원래 for - else를 알고있었는데 for 반복문에도 break가 제대로 적용되는지 헷갈려서 계속해서 while 문을 이용해 코드를 작성하다 보니 변수명을 여러번 사용하고 불필요한 변수들이 들어가 조금 힘들었습니다.

 

그래서 break 관련해서도 검색해 보았고, for 반복문에서도 제대로 동작이 되어서 해당 코드로 작성하였습니다.

 

마지막으로 TypeError가 계속 발생했는데 왜 타입에러가 나는지 이유를 알지 못했습니다.

 

처음에는 deque로 받는거나 혹은 int 인자를 리스트로 받아서 공백이 없어 리스트에 저장해서 문제가 발생하나 싶었는데

 

찾아보니 int 인자를 인덱싱 혹은 슬라이싱 하는게 문제였고 나머지 부분에서 인덱싱은 문제가 없었기에 처음 저장하는 [0] 이 문제구나 라고 생각할 수 있었습니다.

 

그걸 비우고 실행하니 제대로 동작하였고 문제를 해결할 수 있었습니다.