분류 전체보기361 [BOJ]10473번: 인간 대포 https://www.acmicpc.net/problem/10473 suuntree님 풀이를 참고하여 해결하였습니다. (https://suuntree.tistory.com/152) 정점의 수가 작으므로 완전 그래프처럼 생각해도 해결할 수 있습니다. 출발점을 v[0], 도착점을 v[N]이라 놓고 나머지 중간 지점들을 입력받습니다. 특정 정점 N1과 N2의 거리 중 어떤 거리를 취할 지는 아래 두 가지 중 하나를 취하면 됩니다. 1. 대포를 사용하던가 2. 그냥 걸어가던가 두 정점 사이의 거리는 피타고라스 정리를 사용했고, getDistance 라는 함수로 구했습니다. 즉, minTime = min(getDistance(n1,n2)/5 , 2 + (getDistance(n1,n2) - 50) / 5 ) 입니.. 2020. 8. 22. [BOJ]2206번: 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 기본 BFS 유형에서 '벽을 부쉈냐'라는 상태가 추가되었습니다. 벽을 부쉈냐 / 안 부쉈냐라는 상태를 0,1 비트로 표현할 수 있습니다. 즉, 같은 칸을 x,y를 방문했어도 1. 벽을 이미 한 번 부수고 이동하는 상황은 visited[0][x][y]로 표시 2. 벽을 아직 안 부수고 이동하는 상황은 visited[1][x][y]로 표시 이렇게 위 둘은 같은 좌표를 방문했어도 서로 다른 상태가 되는 것입니다. 그러므로 bfs 탐색을 할 때 벽을 부쉈냐 안 부쉈냐까지 고려해서 탐색을 해주면 됩니다. 탐색 종료시점은 벽을 부쉈든 안 부쉈든 N,M 지점에 도착하기만 하면 됩니다. https://github.com/cottory/algorithm/.. 2020. 8. 18. [BOJ]7562번: 나이트의 이동 https://www.acmicpc.net/problem/7562 기본적인 BFS 문제입니다. 나이트가 이동할 수 있는 8칸을 다음 칸 후보로 두고 탐색하면 됩니다. https://github.com/cottory/algorithm/blob/master/BOJ/BOJ7562.cc 2020. 8. 18. [BOJ]1525번: 퍼즐 https://www.acmicpc.net/problem/1525 BFS 문제입니다. 문제를 쉽게 만들 수 있는 방법은 '0'을 '9'로 치환해서 풀면 됩니다. 그러면 맨 앞자리에 0이 오는 경우도 int 자료형으로 처리할 수 있습니다. 정답 숫자는 123456789가 되겠네요. swap을 통해 좌표를 움직여주는 방법은 1차원으로 움직이든, 2차원으로 움직이든 상관없습니다. (저는 1차원 배열 형태로 해결했습니다.) set를 통해 방문했던 상태를 저장하면 해결할 수 있습니다. https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1525.cc 2020. 8. 17. 이전 1 ··· 55 56 57 58 59 60 61 ··· 91 다음
