(BOJ2641 다각형 그리기

• tags : (algorithm

  No matching post could be found

• 문제 링크 : https://www.acmicpc.net/problem/2641
• 풀이 링크
  • Python

• 구현을 통하여 각 모양들이 같은지 확인해야 하는 문제처럼 보이지만, 수열이 주어졌을 때, 해당수열의 변환으로 만들어질 수 있는지 확인하면 된다.
• 변환은 수열을 회전하며 확인하면 되는데, 반대 방향으로도 구현 가능한지 확인해야 한다.

length = II()
target = list(MIIS())
ans = []
for _ in range(II()):
    line = list(MIIS())
    if check(length, target, line):
        ans.append(line)
print(len(ans))
for line in ans:
    print(*line)

• 기본적인 문제 풀이 코드
• 목표 수열 target과 같은 다각형을 만들 수 있는 수열을 저장하는 ans 리스트를 선언
  • 입력을 한줄씩 받으며, 각 수열이 같은 다각형을 만들 수 있는지 확인한다.

def check(length: int, target: list, line: list) -> bool:
    def get_reverse_line(line: list) -> list:
        reverse_table = {1: 3, 2: 4, 3: 1, 4: 2}
        line.reverse()
        for idx, x in enumerate(line):
            line[idx] = reverse_table[x]
        return line

    for _ in range(length):
        if target == line:
            return True
        line = line[1:] + [line[0]]
    line = get_reverse_line(line)
    for _ in range(length):
        if target == line:
            return True
        line = line[1:] + [line[0]]
    return False

• 각 다각형이 같은지 두가지 방향으로 확인한다.
  • 우선, 입력으로 주어진 방향으로 회전하며 확인하고,
  • 거꾸로 그려갔을 때 가능한지 확인한다.
• 거꾸로 그려갈 때는 이동 방향이 반대로 되기 때문에 get_reverse_line()함수를 활용하여 새로운 리스트를 생성한다.