[ 백준 17836 ] 공주님을 구해라! (C++)
[문제보기] [해결과정] 1. 맵 저장 배열(2차원), 방문 체크 배열(3차원), 구조체(y좌표, x좌표, 방문시간, 검획득여부) 큐 생성 2. (0,0)부터 BFS 탐색 시작 2-1. 만약 방문 좌표가 검이 있는 곳이면, 다음 방문확인은 check[y][x][1] 에서 확인. 2-2. 아직 검을 찾지 못했다면, 다음 방문확인은 check[y][x][0] 에서 확인. 3. 공주님을 찾으면 시간 값을 저장하고 return; 위 사진과 같이 검을 안먹었을 때는 check[y][x][0]에서 BFS탐색을 계속하고, 만약 검을 먹었을 경우는 check[y][x][1]에서 검 먹기전 시간을 이어 탐색을 한다. 이때, 검을 먹었을 경우에는 벽을 모두 부술 수 있으니, map 체크를 하지 않아도 된다. (우측 사진처..
2019. 11. 29.
[ 백준 17779 ] 게리맨더링2 (C++)
[문제보기] [해결과정] 1. 기준점 (y,x)를 잡고 기준점으로 부터 왼쪽아래 대각선 (d1)과 오른쪽아래 대각선 (d2)가 갈 수 있는 최대 범위를 완전 탐색 2. 위쪽, 왼쪽, 오른쪽, 아래쪽 점 4개의 좌표 변수를 생성한다. (ty, tx, ly, lx, ry, rx, by, bx) 2-1. 위쪽 좌표는 1번에서의 기준점 (y,x) 2-2. 왼쪽 좌표는 기준점 (y,x)에서 d1만큼 이동한 좌표 ---> ( (y +dy[0] * d1), (x +dx[0] * d1) ) 2-3. 아래쪽 좌표는 왼쪽 좌표 (ly, lx)에서 d2만큼 이동한 좌표 ---> ( (ly + dy[1] * d2), (ly + dy[1] * d2) ) 2-4. 오른쪽 좌표는 기준점 (y,x)에서 d2만큼 이동한 좌표 --->..
2019. 11. 28.
