개발 일지

진행 방향을 꺾어주는것이 포인트인 문제이다. 반대로 돌아가는 경우, 왼쪽으로 꺾는 경우, 오른쪽으로 꺾는 경우가 존재하며, 각 블록은 들어오는 방향에따라 꺾이는 방향이 달라진다. 이를 코드 상단에 보이는 것과 같이 딕셔너리로 표현 가능하며, 핀볼이 이동하는 것은 재귀 함수로도 구현이 가능하나, depth error가 발생하기 때문에 반복문으로 나타내야 한다. 간단하지만 상당히 재밌는 문제라고 생각한다. # 북 서 남 동 dRow = [-1,0,1,0] dCol = [0,-1,0,1] # 북 서 남 동 # 0:back 1:right 2:left blocks = { 1 : [0,1,2,0], 2 : [1,2,0,0], 3 : [2,0,0,1], 4 : [0,0,1,2], 5 : [0,0,0,0] } def ..

문제에서 요구하는 것은 다음과 같다고 생각한다. 데이터를 입력받아 코어의 좌표를 받아올 수 있는가? 각 코어에 전선을 놓는 경우에 대해서, 백트래킹 기법을 이용해 전선이 놓이는 모든 경우를 구할 수 있는가? 전선을 놓는 모든 경우의 수 중, 가장 전선이 많이 놓이는 경우와 그 길이의 합이 최소일 때를 효과적으로 찾을 수 있는가? 이 문제의 핵심이 되는 아이디어는 백트래킹으로의 접근이라고 본다. 하지만 그 결이 조금은 다른데, 전선을 놓는것을 기준으로 봤을 때 백트래킹을 설계한다면 전선을 놓을 수 없는 경우에 가지치기를 해야하나 이 문제에서는 해당 노드를 아예 건너뛰어 버리는 경우까지 고려한다. 결국 모든 노드에대해 전선을 놓을 네가지 방향을 전부 완전탐색을 해준다면 그 경우만 해도 벌써 16,000,00..