BOJ14497

01 Feb 2020 • ProblemSolving

주난의 난

문제출처

문제 해석

  • 주난이가 초코바를 가지고 있는 범인을 찾기 위해 최소로 점프해야 하는 수를 구하는 문제입니다.
  • 주난이가 한번 점프를 하면 파동이 장애물(친구)를 만날 때까지 퍼지게 됩니다.
  • N, M <= 300

설계(10)

  • 범위가 작으므로 dfs를 이용하여 친구들을 만날 때까지 탐색을 한 후, 만나는 친구들의 좌표를 벡터에 저장합니다.
  • 저장된 좌표들을 0으로 변환 후, 파동수를 올려서 다음 탐색을 진행하게 됩니다.
  • 시간복잡도가 O(NM*max(N,M)) 이므로 시간 안에 해결할 수 있습니다.
  • 공개코드 처리된 zagabi님의 코드를 참조해 보면 bfs를 이용해 O(NM)으로 최적화를 할 수 있습니다.

구현(10)

코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#define MAXN 300
using namespace std;

char map[MAXN][MAXN];
bool visited[MAXN][MAXN];
int N, M;

vector<pair<int, int> > v;

bool flag = false;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void dfs(int x, int y) {
	if (flag) return;
	visited[x][y] = true;
	for (int k = 0; k < 4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
		if (visited[nx][ny]) continue;
		if (map[nx][ny] == '0') {
			dfs(nx, ny);
		}
		else if (map[nx][ny] == '1') {
			v.push_back({ nx,ny });
		}
		else if (map[nx][ny] == '#') {
			flag = true;
			return;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	scanf("%d%d", &N, &M);
	int x1, y1, x2, y2;
	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

	x1--;
	y1--;
	x2--;
	y2--;
	for (int i = 0; i < N; i ++ ) {
		for (int j = 0; j < M; j++) {
			scanf(" %1c", &map[i][j]);
		}
	}
	int ans = 0;

	while (!flag) {
		ans++;
		memset(visited, false, sizeof(visited));
		v.clear();
		dfs(x1, y1);
		for (int i = 0; i < v.size(); i++) {
			map[v[i].first][v[i].second] = '0';
		}
	}
	cout << ans << "\n";
	return 0;
}
코드2(최적화)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#define MAXN 300
using namespace std;

char map[MAXN][MAXN];
int dist[MAXN][MAXN];
int N, M;

vector<pair<int, int> > v;

bool flag = false;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	scanf("%d%d", &N, &M);
	int x1, y1, x2, y2;
	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

	x1--;
	y1--;
	x2--;
	y2--;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf(" %1c", &map[i][j]);
		}
	}
	int ans = 0;
	queue < pair<int, int> > q;
	q.push({ x1,y1 });
	dist[x1][y1] = 0;
	while (map[x2][y2] != '0') {
		ans++;
		queue<pair<int, int> > tmp_q;
		while (!q.empty()) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M || dist[nx][ny]) continue;
				dist[nx][ny] = ans;
				if (map[nx][ny] != '0') {
					map[nx][ny] = '0';
					tmp_q.push({ nx,ny });
				}
				else {
					q.push({ nx,ny });
				}
			}
		}
		q = tmp_q;
	}
	cout << ans << "\n";
	return 0;
}
디버깅
제출결과

4ms

마무리

  • 기본적인 탐색방법으로 범위가 작아 깊게 고민하지 않은 문제입니다.
 BOJ

Related Posts