계기
방학동안 알고리즘 스터디를 구성하여 같이 공부하기로 했다. 주최한 친구는 고려대에서 주최하는 대회에 도전하는 것을 목표로 하고싶어했는데, 아직 입문한지 얼마 되지 않아 난이도가 비교적 낮은 순서대로 도전해보자고 상의한 결과 도전하게 된 것이 흐즈로컵이었다.
이번해 출제된 흐즈로컵의 특징은 팀원 간 상의가 가능하며 인터넷 검색이 허용된다는 것이었다. 사실 이 점이 유용하다 생각이 들어 지원한 것도 없잖아 있다. 코로나기간 중 온라인 코테도 비슷한 방식을 취했다고 들었고, 사용법이 익숙치 않아 실패할 경우를 미연에 방지할 수 있기 때문이다. 따라서 풀지 못하는 것은 오로지 내 문제! 이번 문제를 통해 부족한 점을 다시 짚을 수 있는 계기가 되는 것이다.
문제
문제는 총 두 가지로, 각 단계별 문제를 솔브하는 형식이 아니라 여러 개념이 합쳐져 있는 큰 문제를 해결하는 것이 목표였다.
이 중, A1문제를 푸는 것을 목표로 했다.
다른 사람들은 이렇게 출제된 것에서 매우 당황하는 기색을 보였는데, 이전 전공시험에서 이러한 방식의 문제가 출제되었던 경험이 있었기에 문제 자체에서 지레 겁을 먹지는 않았다. 문제는 아직 응용할 수 있는 알고리즘 방식이 적었고, 자료구조를 배우지 않았다는 것이었다. 생각보다 이것이 해당 대회에서는 큰 파이를 차지했다고 본다.
로직
문제는 여태까지 이코테에서 배웠던 구현문제에 기반한 것으로 파악했다. 상하좌우 문제가 8가지의 방향으로 응용되었고 플레이어가 다수로 변경된 점, 목적지가 정해져있고 한 번에 도착할 수 없다는 것이 변형된 포인트라고 생각했다.
따라서 겹치지 않고 목적지에 차례로 들어가기 위해서는 줄을 세워야겠다는 생각이 들었다. 기본적으로 놀이동산같은 경우도 가장 많은 사람을 최소의 공간에 줄을 세우기 위해 지그재그 등의 방식을 사용해 줄을 세운 다음, 차례로 기구에 사람을 배치하는 형식을 취하지 않는가?
그래서 문제를 딱 보고 달팽이 수열처럼 정렬하면 되지 않을까? 라는 생각을 했다. 백준 1913번의 달팽이 문제에서 기인한 풀이었다. 입력을 받은 수를 최댓값으로 한 N*N 범위 내에 도달할 경우 달팽이 수열을 돌리거나, 달팽이 수열이 될 정도로 멀어지게 정렬한 후 그 시작점부터 달팽이 수열을 돌면서 (0,0)에 차례로 들어갈 수 있게 하고 싶었다. 문제는,,달팽이 수열같은 경우에는 이전 백준문제에서 도전하려다 구현에 실패한 문제라는 것이다. 여기서부터 난항을 겪기 시작했다. (구현이 목적인데 구현을 못한다니,,?)
결국 문제의 풀이방식이라도 알아내어 구현하는 알고리즘 코드는 검색하기로 하고, 고민을 더 해봤다.
달팽이 수열을 구현하지 못한다면, 시계방향으로 돌게하는 것이 비슷한 원리가 될 수 있겠다 생각해 좌표를 이대로 정렬하고, 각각의 좌표를 이차원 배열에 저장하는 형식으로 좌표 설정을 세팅했다. 또한, 입력으로 받은 좌표를 (0,0)에 가까운 순서대로 집어넣기 위해 절댓값 기준으로 정렬하면 되지 않을까? 라는 생각을 했지만 이건 필요없는 듯 하다.
여기서부터는 두 개의 방식이 갈렸는데, 한 좌표를 먼저 받아 그 좌표가 (0,0)에 도달할 경우 배열에서 POP하고 배열에 아무것도 없을 때까지 반복을 하거나, 입력된 모든 좌표를 한 번씩 이동시켜주어 (0,0)에 도달할 경우 POP한 후 똑같이 진행할 수 있을 것이라는 생각이 들었다. 왜나하면 문제에서 각 좌표는 매번 움직여야 하고, 겹쳐서는 안되며 이전에 방문한 좌표를 재방문해서는 안되기 때문에 재방문과 겹치는 여부에 대한 처리가 위 방식에 따라 달라질 것이라 생각이 들었기 때문이다.
'''
입력받은 개수만큼 좌표를 만들어 정렬(절댓값이 0, 0에서 제일 가까운 것 순서대로?)
수열 안에 들어오는 사람부터 달팽이 수열 스타트
처음부터 좌표를 시계방향으로 정렬한다면?
근데 이차원 배열 요소는 배열이라 좌표 이동 사용이 불가함,,
'''
'''
좌표를 시계방향으로 정렬한 후 , 각각의 좌표를 받아 이차원 배열에 저장함.
각 좌표를 절댓값 기준으로 재정렬
while true 반복문을 돌면서 첫번째 좌표에 있는 용사부터 0,0으로 이동시킴
[동시에 겹치는 부분을 어떻게 처리? -> 한명씩 dfs하거나, 여러명을 bfs 하듯이?]
이동값에 해당되는 알파벳을 리스트에 저장
visited 배열을 만들어서 이동이 끝날 때마다 좌표값을 넣어줌(재방문 금지용)[만일 한 명 dfs 돌리듯이 처리할 것이라면, 이 부분에 대한 처리가 필요함]
0,0에 도달하면 해당 리스트에서 뺌
최종 길이가 0에 도달하면 break를 걸어 탈출한 후 리스트 안의 값을 차례로 출력
'''
import sys
input = sys.stdin.readline
n = int(input()) #입력값
n_list = [] #좌표값
plans = [] #이동값 출력할 리스트
# key = ['A', 'Q', 'W', 'E', 'D', 'C', 'X', 'Z']
# key_dict = dict(zip(key, list(range(len(key)))))
#move = {'A':[-1, 0], 'Q':[-1, 1], 'W':[0, 1], 'E':[1, 1], 'D':[1, 0], 'C':[1, -1], 'X':[0, -1], 'Z':[-1, -1]}
# dx = [-1,-1, 0, 1, 1, 1, 0, -1]
# dy = [0, 1, 1, 1, 0, -1, -1, -1]
#시계방향 정렬
dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]
mapper = {'W':0, 'E':1, 'D':2, 'C':3, 'X':4, 'Z':5, 'A':6, 'Q':7}
#각각의 좌표 받기
for k in range(n):
x, y = map(int, input().split())
n_list.append([x, y])
#n_list.append((i, j))
while(True): #모든 요소가 0, 0에 도달할 때까지
#각각의 좌표에 대해 입력값을 한번에 바꾸고 싶은데
for i in range(8): #8방향에 대해서
nx = x + dx[i][0]
ny = y + dy[i][1]
#좌표 안 겹치면(리스트의 값이 같지 않으면)
plans.append() #움직인 좌표값에 해당되는 값을 넣어줌
x, y = nx, ny
#0,0에 도달하면 리스트에서 제외
if n_list[[x, y]] == 0:
n_list.pop()
if not n_list: #리스트에 아무것도 없으면
break
#시계방향 정렬
for m in plans:
print(*m, sep = '')뭐,, 하지만 근본적인 문제를 해결하지 못해 실패 처리를 받았다.
에디토리얼
추후에 올라온 에디토리얼을 보고 접근 자체가 잘못되지는 않았다는 생각이 들었다. 많은 분들이 1913번의 문제를 전처리한 방식으로 해결한 것을 확인했기 때문이다. 하지만 그와는 별개로 문제를 많이 풀어보지 않아 로직 자체를 코드로 옮기지 못한 분명한 한계를 깨닫고 문제를 많이 풀어봐야겠다고 느끼게 되었다.
여담
이렇게 참담한 중간과정과는 별개로, 특별상에 당첨되었다!
이번엔 구글폼에 인증샷이 첨부되지 않아 상품을 타가지 못했다..구글링 해도 해결이 되지 않아 참 속상했다. 여러모로 어려운 대회였다는 생각이 든다. (+ 보상으로 받은 뱃지가 참 이쁘다!)
주최해주신 분들과 문제출제진, 검수자분들 그리고 후원해주신 모든 분들께 감사하다는 말씀을 올리고 싶다.