백준 15685 드래곤 커브 - (Python)

문제

출처: https://www.acmicpc.net/problem/15685

나의 접근법

처음 문제를 접했을 때 너무 특이한 문제라서 당황했습니다. 90도 시계방향 회전을 어떻게 다뤄야 할지 감이 안잡혔습니다. 그래서 최대한 규칙을 찾으려고 노력했습니다.

 

일단 제일 눈에 띄는 점의 좌표 변화를 파악하여 규칙성을 찾으려고 노력했습니다. 하지만 세대가 커질수록 점의 좌표는 이전 세대의 좌표들과 너무 크게 벌어지고 규칙성도 없다는 느낌이 들어서 빠르게 포기했습니다.

 

다음은 방향의 변화들로 규칙성을 찾으려고 노력했습니다.    

방향을 기준으로 하니 답이 보였습니다. 4 4 1 3 의 경우 윗 방향으로 3세대까지 드래곤이 커브를 하는데 다음 커브의 순서가 이전 커브 역순에서 +1 한 것이었습니다. 자세한 그림은 다음과 같습니다.

리스트에 추가되는 방향의 번호가 이전 번호를 stack처럼 빼서 +1 하여 2세대 리스트와 병합하면 되었습니다.

 

정답 코드

import sys
def sol(graph, x, y, d, g):
    #일단 0세대만 만들기
    gen0 = []
    gen0.append(d)
    res = gen0[:]
    for i in range(1, g+1):
        tempGen = res[:]
        while tempGen:
            res.append((tempGen.pop()+1)%4)

    graph[y][x] = 1
    for i in res:
        x, y = x + dir[i][0], y + dir[i][1]
        graph[y][x] = 1

N = int(sys.stdin.readline().rstrip())
graph = [[0]*101 for i in range(101)]
dir = [(1,0), (0,-1), (-1,0), (0,1)] # → ↑ ← ↓
for i in range(N):
    x, y, d, g = map(int, sys.stdin.readline().split())
    sol(graph, x, y, d, g)

#findSquare
ans = 0
for i in range(100):
    for j in range(100):
        if graph[i][j] == 1 and graph[i+1][j] == 1 and graph[i][j+1] == 1 and graph[i+1][j+1] == 1:
            ans += 1
print(ans)

결과 

처음에는 100x100 사이즈인데 101*101 크기로 graph를 설정하지 못해 인덱스 에러가 발생했습니다. 그래도 바로 고쳐서 시간을 아낄 수 있었습니다.

 

오랜만에 "삼성 SW 역량 테스트 기출 문제" 를 정답이나 도움 없이 스스로 처음부터 끝까지 해결했습니다.

며칠 전부터 계속 답을 못찾고 에러 발생하고 원하는 결과가 안나와서 코딩 테스트를 풀 때 마다 큰 자괴감과 자책속에 빠졌었는데 이렇게 답을 맞추니 정말 기분이 좋았습니다.

 

계속 물고 늘어지며 문제를 접근하는 방법과 그 방법을 코드로 깔끔하고 완벽하게 짜는 것이 정말 중요한 것 같습니다.

이 문제는 그리디, 백트래킹 같은 알고리즘보다 문제 속의 규칙을 빠르게 찾는 것이 중요했던 것 같습니다.

저도 이 문제를 빠르고 한번에 풀어서인지 정답률이 그리 낮진 않았습니다.

다음에는 더 어려운 문제를 도전해서 이번처럼 풀어 보고 싶습니다.