본문 바로가기

Algorithm/BOJ172

[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.
[BOJ]10217번: KCM Travel https://www.acmicpc.net/problem/10217 바킹독님 풀이를 통해서 해결했습니다. (https://blog.encrypted.gg/164) DP[i][j]: "1번 노드부터 i번 노드까지 비용 j를 써서 갈 때의 최소 시간"으로 상태를 정의합니다. 예외 조건은 j 값이 M을 초과하면 예외입니다. (continue) 이렇게 상태를 정의하고 1번 노드부터 다익스트라를 돌리면, "비용 M 이하" 조건을 만족하는 경로 중에서 가장 먼저 N번 노드에 도착하는 경로가 최소 시간을 만족하는 정답입니다. https://github.com/cottory/algorithm/blob/master/BOJ/BOJ10217.cc 2020. 8. 17.

티스토리툴바