[BOJ 24515] 백준 24515번 - 히히 못가
1. 문제
$24515$. 히히 못가 (2022 ICPC Sinchon Winter Algorithm Camp Contest G번)
2. 풀이
로미오는 가장 왼쪽 위 칸, 줄리엣은 가장 오른쪽 아래 칸으로 위치가 고정되어 있다는 점이 중요하다.
이 조건 때문에 세 번째 그림과 같이 오른쪽 위($0$)에서 왼쪽 아래($1$)를 가로지르는 직선 하나를 그으면(또는 그림의 $0$에서 $1$로 향하는 직선 하나만 그으면), 로미오가 줄리엣과 만나는 것을 막을 수 있다.
따라서 특정 개수의 영역을 구매하여 위에서 서술한 방향의 직선을 완성하되, 최소 개수의 땅을 구매하는 방법을 찾아내는 것이 풀이 방법이 된다.
시작 영역인 위쪽과 오른쪽은 group index를 $0$으로, 도착 영역인 왼쪽과 아래쪽은 group index를 $1$로 초기화시킨다.
- BFS를 통해 각 땅이 속하는 영역을 구분한다. (두 번째 사진)
- BFS를 통해 각 영역이 인접해 있는 영역을 알아낸다. (각 영역이 node, 인접 정보가 edge, 영역의 땅 개수가 weight가 된다.)
- 알아낸 node와 edge, weight를 토대로, 다익스트라를 돌려서 오른쪽 위에서 왼쪽 아래로 가는 최소 경로의 땅 개수를 알아낸다.
$1$을 수행할 때, ‘어떤 두 칸의 알파벳이 같더라도 연결되어 있지 않다면, 다른 영역에 속할 수 있다.’라는 점에 유의해야 한다. 첫 번째 그림처럼 알파벳이 같더라도 인접하지 않았으므로, 두 번째 그림과 같이 서로 다른 영역이 된다.
$2$에서 인접한 영역을 알아내는 데에는 BFS를 사용하였다. 다만, 이미 인접한 영역임을 확인했음에도 다시 확인하여 edge vector에 추가해버리는 상황이 발생하다보니 set 자료구조를 통해 중복을 없애야 했다. Set에 insert하고 탐색하면서 시간을 쓸데없이 낭비해버렸다. 아마 인접한 영역을 알아내는 더 좋은 방법이 있을 것이다.
직선과 같은 형태를 만드는 것이기 때문에, 각 영역들은 상하좌우 뿐만 아니라 대각선으로 연결되어도 된다는 점에 유의한다.
알아낸 node와 edge, weight를 토대로 $0$에서 시작하는 다익스트라를 돌리면, $1$까지의 최소 거리를 알아낼 수 있고 이것이 정답이 된다.
3. 채점 결과
4. 회고
.
댓글남기기