-
[BOJ - 5558] チーズ카테고리 없음 2020. 4. 3. 02:12
https://www.acmicpc.net/problem/5558
5558번: チーズ
入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 ≦ H ≦ 1000，1 ≦ W ≦ 1000，1 ≦ N ≦ 9) がこの順に空白で区切られて書かれている．2 行目から H+1 行目までの各行には，'S'，'1', '2', ..., '9'，'X'，'.' からなる W 文字の文字列が書かれており，各々が各区画の状態を表している．北から i 番目，西から j 番目の区画を (i,j) と記述することにすると (1 ≦ i ≦ H, 1 ≦ j ≦ W)，第 i+1 行目の j 番目
www.acmicpc.net
일본 문제다.
쥐가 치즈를 찾아서 가는 문제
최초 사이즈가 1이고, 그에 동등한 치즈를 먹음으로서 사이즈를 늘릴수있다.
맵에 주어져있는 모든 치즈를 먹기 위해 최단거리로 이동하는 거리를 묻는 문제다.
나는 BFS를 통해 문제를 풀었는데, 한가지 쉽게 느껴질수 있는 부분은
먹어야 하는 치즈의 개수가 생각보다 적다는 것이다.(9개 이하)
그래서 방문 배열을 만들때 1000x1000x11 정도로 세워두면 큰 트러블 없이 문제를 풀수있다.
또하나 주의할 점은, 맵이 생각보다 작지는 않기 때문에 치즈를 먹고 커버린 사이즈보다 작았을 시절에
탐색했던 Queue의 원소들은 탐색을 중지시키는 과정이 필요하다.
나는 dost 배열로 사이즈를 이미 해결했다! 라는 의미로 사용했고, 이미 해결했으면 더이상 탐색하지 않고 끝내는 방식으로 시간 조절을 해줬다.