(python3) https://www.acmicpc.net/problem/15685 문제 조건을 잘 읽어봐야합니다. 드래곤 커브가 격자 밖으로 빠져나가지 않는다는 조건 하나로 문제가 간결해집니다. 그리고 네모 변이 다 그려진 칸의 개수가 아니라 4개 점이 모두 드래곤 커브에 포함되는게 조건이라 이 부분도 파악하고 있어야합니다. 헷갈릴만한 부분들인것 같습니다. 구현 디테일 다음 세대에 포함될 점들을 찾아내는게 메인 파트입니다. 저는 항상 배열의 마지막 점이 다음 세대 드래곤 커브를 만드는 기준점이 되도록 다음 세대 점을 계산할 때 뒤쪽 점부터 계산했습니다. 기준점을 기준으로 시계방향 90도 회전한 점의 좌표 계산식만 헷갈리지 않고 작성하면 될 것 같습니다. 끝! 코드 def solution(input) ..
(python) 아이디어 일단 연속된 숫자가 L 번 이상 나와야 경사로를 놓을 수 있고, 1칸 차이여야 경사로를 배치해서 지나갈 수 있습니다. 핵심이 되는 아이디어는 "길의 표현법을 수정해서 연속된 번호의 횟수로 표현하겠다" 입니다. (층,연속횟수) 의 배열로 나타냈습니다. (지금은 튜플로 표현했지만 뒤에서 연속횟수를 변경해주어야해서 코드 상에서는 list 를 사용했습니다.) 예를 들어서 [3 2 1 1 2 3] 를 [(3,1), (2,1), (1,2), (2,1), (3,1)] 로 표현을 바꿔주는겁니다. 이렇게 바꾸면서 1. 층이 바뀌는 부분을 바로 알 수 있다. 2.경사로를 놓을 수 있는지 바로 체크할 수 있다. 두가지 장점이 생깁니다. 여기에서 층이 바뀔때마다 1층씩 변경됐는지, 1층 변경됐으면 경..
(python3) 아이디어 까다로운 상어 시리즈의 청소년 버전입니다. 이 문제는 시뮬레이션의 조건이 많기 떄문에 코딩 과정에서 스텝이 꼬이지 않도록 기능을 잘 분리해서 접근해주는게 좋습니다. 저는 위치가 2차원 행렬로 표현되는 경우 x,y 보다 r,c 를 사용하는게 명료해서 더 선호합니다. 방향 역시 1~8 의 숫자로 문제에서 주어졌지만 배열로 접근할때의 편의성을 위해 0~7 로 변환하여 사용했습니다. 이런 디테일한 변수 설정들이 헷갈리지 않도록 메모하거나 체계를 잡아두는게 좋은 것 같습니다. 상어가 이동할 수 있는 모든 경우의 수를 탐색해야하고, 이전의 선택 뒤에 다음 선택지가 가지치듯 갈라지는게 반복되기 때문에 백트레킹을 사용하는게 좋습니다. 재귀를 활용해서 단순하게 구현이 가능합니다. 백트래킹은 트..
(python3) 구현 아이디어 각 기능을 구현한 함수명을 함께 작성했습니다. 1. 벽 3개를 세울 수 있는 모든 방법을 찾아야 합니다. next() 는 바로 다음 빈칸을 찾습니다. next_wall() 에서는 다음 벽 3개 조합을 찾습니다. 3번 벽을 한칸 다음으로 옮겨보고, 옮길 공간이 없으면 그 2번 벽을 한칸 다음으로, 3번 벽은 2번 벽 바로 다음으로 배치합니다. 이때 3번 벽이 또 갈 곳이 없다면 1번 벽을 한칸 다음으로 옮기고 그 다음에 2번, 그 다음에 3번 벽을 배치합니다. 이때 3번 벽을 배치할 공간이 없으면 모든 벽의 조합을 다 확인해본 꼴이 됩니다. 2. 벽을 세우고, 맨 처음 배치되어 있는 모든 바이러스에 대해 dfs 를 수행하여 바이러스가 다 퍼진 뒤의 상태를 확인합니다. (in..
