반응형
문제
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
풀이
BFS로 풀이할 수 있는 문제입니다.
벽을 한 번도 안부수고 이동하는 것과, 한 번 부수고 이동하는 것을 나누어서 생각해야합니다.
벽을 부시고 그 좌표를 방문했는지, 한 번도 안부수고 방문했는지를 나타내기 위해 3차원 Bool 배열을 사용하였습니다.
벽을 안부셨다면 다음 이동할 좌표가 0이면 그냥 방문하면되고, 1이라면 벽을 부시고 방문할 수 있습니다.
벽을 한 번 부셨다면 다음 이동할 좌표가 0이면 방문할 수 있지만, 1이라면 방문할 수 없습니다.
BFS 함수안에서 이 두 경우를 나누어서 최단 거리를 알 수 있습니다.
소스코드
후기
벽을 부순 여부를 알기 위해 3차원 배열을 떠올려서 풀었던 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 3085 사탕 게임 (Swift) (0) | 2023.06.02 |
|---|---|
| [BOJ] 백준 18352 특정 거리의 도시 찾기 (Swift) (0) | 2023.06.02 |
| [BOJ] 백준 9205 맥주 마시면서 걸어가기 (Swift) (3) | 2023.05.26 |
| [BOJ] 백준 2162 선분 그룹 (Swift) (0) | 2023.05.25 |
| [BOJ] 백준 20149 선분 교차 3 (Swift) (0) | 2023.05.25 |
