알고리즘 풀이/백준(Boj)
백준(BOJ) 1175번 배달
100win10
2020. 3. 8. 04:16
문제 : https://www.acmicpc.net/problem/1175
1175번: 배달
어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다. 입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다. S : 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이다. C : 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하
www.acmicpc.net
풀이 :
BFS를 통해 최소 거리를 구해주었는데 이때 d는 4차원으로 잡았다. 그 이유는 4가지 방향 배열에 의해서
각각의 경우가 다르기 때문에 그리고 Status로 C를 하나 방문한 경우를 정해주어야 한다.
Status의 경우 예를 하나 들어보자
2 2
SC
C#
위의 경우는 C를 가지고 S를 다시 거쳤다가 가야 한다. 하지만 방향 배열만 추가한 3차원으로만 정의했다면
첫 번째 C를 방문하고 다시 두 번째 C를 방문할 수 없다. 이미 첫 방문 때 방문되었기 때문
따라서 상태배열까지 추가해줘야 한다.
코드에 nst |= 1과 nst |= 2는 똑같은 C를 두 번 방문했을 경우를 방지하는 방법이다.
단순히 nst += 1 나 += 2로 한다면 똑같은 경우를 방문해도 카운트 되게 된다. 이를 방지하기 위해 사용하였다.
코드 ( C++ )
