[ BFS | 연습문제] 1697번 : 숨바꼭질

https://www.acmicpc.net/problem/1697

---

 걸린 시간 

1시간

 

 생각

 y축이 없는 bfs라고 생각

1회 제출 : 틀림 ( 같은 위치에 있는 경우를 생각하지 않음)

2회 제출 : 틀림 ( 같은 위치에 있을때 1초로 계산해서 틀림)

3회 제출 : 정답 ( 같은 위치 있을때 0초로 수정)

---

 구현 코드 

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;


int board[100001];
int visit[100001];
int dx[3] = { -1,1,2 };
int n, k;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	fill(visit, visit + 100001, -1);

	queue<int> q;
	cin >> n >> k;
	board[k] = 1;	//동생 위치

	board[n] = 1; //수빈이 위치
	q.push(n);
	visit[n] = 0;

	if (n == k)
	{	//같은 위치에 있으면 바로 찾으니까 0 출력하게 함
		cout << 0;
		return 0;
	}
	while (!q.empty()){
		int cur = q.front(); q.pop();

		for (int dir = 0; dir < 3; dir++){
			int nx;
			if (dir == 2)
				nx = cur * dx[dir];
			else
				nx = cur + dx[dir];

			if (nx < 0 || nx>100000) continue; //수빈이가 범위 벗어나면 pass
			if (visit[nx] < 0){
				if (board[nx] != 1){
					q.push(nx);
					visit[nx] = visit[cur] + 1;
				}
				else{//board[1] 이면 동생 찾은거라서 종료
					visit[nx] = visit[cur] + 1;
					cout << visit[nx];
					return 0;
				}
			}
		}
	}
}

 

 리뷰 

이 문제에서는 거리 계산만 해주면 되기때문에 board[] 을 안쓰고도 가능했다. 

실제로 나도 board로 동생이 있는지 없는지 판단하는데에만 사용했는데 동생이 있는 위치를 알고 있으니 굳이 안써도 됐다.

난 while문을 q가 빌 때까지 돌도록 짜서 동생을 찾고나서도 계속해서 BFS를 돌까봐 return문을 따로 넣어주었는데 visit[동생위치]의 방문여부를 조건문으로 삼으면 안해도 됐다.

그리고 같은 위치일 때도 따로 처리하지 않아도 된다..!

 

물론 정답은 없지만 효율적인 코드를 짤 수 있도록 생각해보자