[백준] 2564번: 경비원

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

2564번: 경비원

 

 

나는 처음에 BFS를 이용해서 풀었다.

근데 알고보니 BFS까지 필요없는 문제였다. 

1. BFS

문제 이해

맵을 X+1 * Y+1 로 바꿔서, 동근이 위치로부터 특정 위치까지의 경로를 BFS로 visited 배열에 찍어두고,

각 상점 좌표에 있는 값을 답으로 찍어주었다. 

주어진 맵이

이렇게 생겼다면, 

 

나는 맵을 다시

이렇게 구성해서 D를 시작점으로 해서 BFS를 돌렸다.

대신 저 하얀 부분은 못가도록 막고 (시작 전에 visited[]의 값을 1로 바꿔둠) 시작한다.  

그럼 최단 거리가 1, 2, 3 자리에 찍힌다. 

작성 코드

#include <stdio.h>
#define NORTH 1
#define SOUTH 2
#define WEST 3
#define EAST 4

// 입력 변수
int X, Y;
int N;
int s[100 + 10][2];
int dir, far;

int visited[100 + 10][100 + 10]; // BFS 시 방문 표시
int curx, cury;

// 방향 벡터
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };

typedef struct POS {
	int y;
	int x;
	int time;
}POS;

POS q[100 * 100 + 10];
int rp, wp;

void enq(int y, int x, int time) {
	q[wp].y = y;
	q[wp].x = x;
	q[wp].time = time;
	wp++;
}

POS deq() {
	POS tmp = q[rp];
	rp++;
	return tmp;
}

int isEmpty() {
	return rp == wp;
}

void getPos(int d, int f) {

	if (d == SOUTH) {
		cury = Y;
		curx = f;
	}
	if (d == NORTH) {
		cury = 0;
		curx = f;
	}
	if (d == WEST) {
		cury = f;
		curx = 0;
	}
	if (d == EAST) {
		cury = f;
		curx = X;
	}
}

void BFS(int sy, int sx, int time) {

	enq(sy, sx, time);
	visited[sy][sx] = time;

	while (!isEmpty()) {

		POS cur = deq();
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];

			if (ny<0 || ny>Y) continue;
			if (nx<0 || nx>X) continue;
			if (visited[ny][nx] != 0) continue;

			enq(ny, nx, cur.time + 1);
			visited[ny][nx] = cur.time + 1;
		}
	}

}

void getInput() {
	int d, f;
	scanf("%d %d", &X, &Y);
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &s[i][0], &s[i][1]);
	}
	scanf("%d %d", &dir, &far);
}

int main(void) {

	int sum = 0;
	getInput();

	for (int i = 1; i < Y; i++) {
		for (int j = 1; j < X; j++) {
			visited[i][j] = 1;
		}
	}

	getPos(dir, far);
	BFS(cury, curx, 0);

	for (int i = 0; i < N; i++) {
		getPos(s[i][0], s[i][1]);
		sum += visited[cury][curx];
		//printf("%d ", visited[cury][curx]);
	}

	printf("%d", sum);

	return 0;
}

 

 

2. 상대적인 위치 파악

그냥 상점의 위치와 동근이의 위치를 어느 한 지점에서의 상대적인 거리로 파악하면 된다.

(주의할 점은 방향은 항상 같아야 한다는 것!!)

그런 후에 비교할 위치의 상대적 거리간의 차이를 구한다. 

예를 들어 1과 X 사이의 거리를 구한다면 |22-4| = 18이다.

만약 이 값이 가로 세로의 합, 즉 10+5 = 15 보다 크면 반대 방향이 더 가깝단 소리이다.

총 둘레인 30-18 = 12 하면 12가 최종적으로 1과 X 간의 거리가 되는 것이다. 

 

이걸 코드로 구현하면 훨썬 간단하게 답을 찾을 수 있다!