[시즌2] 6146번 신아를 만나러

0. 문제

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

6146번: 신아를 만나러

문제

키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. 각각의 웅덩이는 (Ai, Bi)(|Ai| ≤ 500, |Bi| ≤ 500)에 위치해 있으며 키파는 눈이 좋아 이 웅덩이를 모두 볼 수 있다.

신아가 일찍 일어날 수도 있기 때문에 어서 (X, Y)에 있는 신아의 집에 최대한 빨리 도달해서 그녀가 잘 때 서프라이즈를 해 주고 싶지만, 장화가 새 것이기 때문에 웅덩이를 밟지 않는 것도 중요하다. 만일 키파가 상하좌우로만 이동할 수 있다면 웅덩이를 밟지 않으면서 신아에게 갈 수 있는 최소 거리는 얼마인가? 신아에게 가기 위해 웅덩이를 밟아야만 하는 경우는 없다고 가정한다.

입력

첫째 줄에 X, Y와 N이 공백을 사이에 두고 주어진다.

i+1 (1 ≤ i ≤ N) 번째 줄에 Ai와 Bi가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 키파가 웅덩이를 밟지 않고 신아에게 갈 수 있는 최소 거리를 출력하라.

1. 문제 분석

"키파가 상하좌우로만 이동할 수 있다면 웅덩이를 밟지 않으면서 신아에게 갈 수 있는 최소 거리는 얼마인가?"

- 웅덩이라는 갈 수 없는 그리드가 존재합니다. 이것을 피하면서 도달하기 위해서는 BFS를 사용해도 될 것 같다.

"신아에게 가기 위해 웅덩이를 밟아야만 하는 경우는 없다고 가정합니다."

- 무조건 신아에게 도착하기 때문에, 도착 못할 것이라는 생각은 하지 않아도 좋다.

"예제로 주어진 입력, 출력값을 보자!"

- 굉장히 귀찮은 문제이다. 나는 이런 문제를 좋아하지 않는다. 왜냐하면 잘 못풀기 때문에!

- 음수 값도 들어가 있기 때문에, 그냥 범위를 설정하면 되겠지만 나는 양수로 바꾸어서 문제 푸는 것을 좋아한다. 그리고 수학에서 쓰이는 그래프 형식으로 되어있기 때문에 이것을 우리가 주로 쓰는 메모리 위치형식으로 바꾸어야 하기 때문에 조금 머리를 굴려봅시다.

- 모든 값의 범위는 -500 ~ 500이다. 그렇다면 500씩 전부 다 당겨야 한다.

- x의 값이 양수다? 500을 더한다.

- x의 값이 음수다? 음수의 값만큼 이동한 것이기 때문에 양수로 바꾸기 위해서는 -1을 곱하고 그 값만큼 더해야한다. 그리고 1000에서 x를 빼야한다. 이유는 음수만큼 간 거리를 빼기 위해서는 500에 더하고 그 값을 전체 길이에서 빼줘야 하기 때문이다. 직접 계산해보면 안다.

- y가 양수라면? 그대로 더하고, 1000에서 빼면 된다.

- y가 음수라면? 똑같이 하면 된다.

2. 왜 이렇게 접근했는가?

BFS를 이용해서 문제를 해결할 수 있겠다. 어찌됐든 모든 길을 돌면서 탐색을 해야하기 때문에 BFS를 이용해 문제를 해결할 수 있을 것이라 생각했다.

3. 예외 케이스는 무엇이 있을까?

예외 케이스는 도달하지 못할 경우가 존재하는데, 문제에서 도달하지 못할 일은 없다고 했다. 그렇다면 예외 케이스는 고려할 필요는 없을 것이다.

4. 빠른 구현을 위한 기술 또는 구현 방식

평범한 BFS 문제이다. 그리고 좌표 이동하는 문제인데 이거 나도 잘 못한다. 매번 손으로 끄적거리는데 어떻게 빠르게 생각할 수 있을지 고민해봐야겠다. 다른 사람들은 그냥 뚝딱뚝딱하던데 나는 못해..요.

5. 구현

#include<iostream>
#include<queue>

#define MAX 1001
using namespace std;

const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};

int hy,hx,poolCnt,board[MAX][MAX],visited[MAX][MAX];
pair<int,int> home;

void printBoard() {
	
	cout << "print board!" << "\n";
	
	for(int i = 496; i <= 510; i++){
		for(int j = 499; j <= 510; j++){
			cout << board[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}

pair<int,int> func(int x, int y){
	
	if(x > 0){
		x = 500 + x;
	}
	else{
		x = 500 + (x * -1);
		x = 1000 - x;
	}
	if(y > 0){
		y = 500 + y;
		y = 1000 - y;
	}
	else{
		y = 500 + y;
		y = 1000 - y;
	}
	
	return {x,y};
}

void init() {
	
	cin >> hx >> hy >> poolCnt;
	
	for(int i = 0; i < poolCnt; i++){
		int x,y;
		cin >> x >> y;	
		pair<int,int> a = func(x,y);
		
		//cout << "x : " << a.first << " " << "y : " << a.second << endl;
		
		board[a.second][a.first] = 1;
	}
	
	home = func(hx,hy);

}

struct info{
	
	int y;
	int x;
	int cnt;
	
};

bool isRange(int y, int x){
	return 0 <= y && y < 1001 && 0 <= x && x < 1001;
}

int ans = -1;

void bfs() {
	
	queue<info> q;
	q.push({500, 500,0});
	visited[500][500] = 1;
	
	while(!q.empty()){
		
		int y = q.front().y;
		int x = q.front().x;
		int cnt = q.front().cnt;
		q.pop();
		
		if(home.second == y && home.first == x){
			ans = cnt;
			break;
		}
		
		for(int i = 0; i < 4; i++){
			
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(!isRange(ny,nx)) continue;
			if(board[ny][nx]) continue;
			if(visited[ny][nx]) continue;
			
			visited[ny][nx] = true;
			q.push({ny,nx,cnt+1});	
		}
		
	}
	
}

int main() {
	
	init();
	bfs();
	cout << ans;
	
	return 0;
}

* 문제 풀이는 항상 C++ 로 진행하고 있습니다.

* 해당 글에 대한 댓글 달아주시면, 심도 깊이 생각해 답글 달아드리겠습니다.