백준(BOJ) 1175번 배달

문제 : https://www.acmicpc.net/problem/1175

1175번: 배달

풀이 :

 

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++ )