글 읽기 - 반례 질문 및 알고리즘 질문드립니다.. !

lswoo3021 5년 전 1

안녕하세요 .. ! 또 이렇게 질문을 드리네요 ㅠㅡㅠ

이번 문제도 역시 .. TC는 맞는데 오답으로 나오네요 ..ㅠ

반례가 있다면 부탁드리겠습니다.
문제의 접근 방법을 잘 몰라서 이래저래 풀었는데... 방법이 맞나요 ? (혹시 더 간편한 방법이 있다면 레퍼런스좀 부탁드려도 될까요 !! )

-최단거리를 찾을 때 visit[][]배열 외에 최단거리를 저장하는 distp[][]를 두어

현재 노드의 거리(dist[x + dx][y + dy]) = 이전 노드의 거리(dist[x][y]) + 1 로

모든 정점에 대해 최단거리 맵을 정리함.

-> 기출 문제중 bfs의 최단거리 문제는 처음보는 것 같네요... 일반적인 bfs에서

최단거리(또느 깊이, 레벨)을 파악하기 위해 약간의 변형이 필요한 문제.. 맞나요 ?

보통은 ㅠㅡㅠdfs든 bfs든 모든경우의수를 돌린뒤 min이나 max를 통해 단순비교하여 최소값/최댓값을

찾았는데요... 제가 너무 안일하게 생각했나봐요 ㅠ

정답률이 50%가 넘는데 다들 ㅠㅡㅠ 대단하신거같아요!

저는 bfs에서 거리를 기록하는 방법을 잘몰라서 헤맸는데 말이져 ㅠㅡㅠ

감사합니다!

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX_SIZE 20

using namespace std;

int map[MAX_SIZE][MAX_SIZE];
int visit[MAX_SIZE][MAX_SIZE];
int dist[MAX_SIZE][MAX_SIZE] = { 0 , };
int n;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};


typedef struct bok {
	int x, y, size, food;
}bok;

typedef struct point {
	int x, y;
}point;

typedef struct target {
	int x, y, dist;
}target;


int minDist = 2 * 20;
int gameTime = 0;
target t1;
bok b1;

void getInput() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {	// 복어 위치
				b1.x = i;
				b1.y = j;
			}
		}
	}
	b1.size = 2;
	b1.food = 0;
}

void getSampleInput() {
	n = 20;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map[i][j] = 1;
			b1.x = n / 2;
			b1.y = n / 2;
		}
	}
	b1.size = 2;
	b1.food = 0;
}

int bfs(int x, int y) {
	queue <point> q;
	point p;
	p.x = x;
	p.y = y;
	q.push(p);
	//int len = 0;
	int find = 0;
	

	while (!q.empty()) {
		point next;
		p = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			
			next.x = p.x + dx[i];
			next.y = p.y + dy[i];
			if (next.x < 0 || next.y < 0 || next.x >= n || next.y >= n) continue;
			if (visit[next.x][next.y] == 1) continue;
			if (map[next.x][next.y] > b1.size) continue;
			visit[next.x][next.y] = 1;
			dist[next.x][next.y] = dist[p.x][p.y] + 1;	// 거리 갱신
			if (map[next.x][next.y] >= 1 && map[next.x][next.y] <= 6 && map[next.x][next.y] < b1.size) {
				// 먹이 발견 
				find = 1;
			}
			q.push(next);
		}
	}
	dist[b1.x][b1.y] = 2 * 200;
	int mx=b1.x, my=b1.y;
	if (find == 1) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (dist[i][j] < dist[mx][my] && map[i][j] >= 1 && map[i][j] <= 6 && map[i][j] < b1.size) {
					mx = i;
					my = j;
				}
				else if (dist[i][j] == dist[mx][my] && map[i][j] >= 1 && map[i][j] <= 6 && map[i][j] < b1.size) {
					if (i < mx) {
						mx = i;
						my = j;
					}
					else if (i == mx) {
						if (j < my) {
							mx = i;
							my = j;
						}
					}
				}
			}
		}
		t1.dist = dist[mx][my];
		t1.x = mx;
		t1.y = my;
	}

	return find;
}

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visit[i][j] = 0;
			dist[i][j] = 0;
		}
	}
}

void showStatus() {
	cout << "gameTime = " << gameTime << " s " << "bok_size : " << b1.size << ", bok_food : " << b1.food << endl;
	cout << "map is below" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 9) cout << "*" << " ";
			else cout << map[i][j] << " ";
		}
		cout << endl;
	}
}

int main() {
	
	getInput();

	//getSampleInput();
	while (true) {
		int ret = bfs(b1.x, b1.y);
		if (ret == 0) break;
		gameTime += t1.dist;
		map[b1.x][b1.y] = 0;
		b1.x = t1.x;
		b1.y = t1.y;
		b1.food++;
		map[b1.x][b1.y] = 9;
		//showStatus();

		if (b1.food == b1.size) {
			b1.size++;
			b1.food = 0;
		}
		init();

	}

	cout << gameTime << endl;
	int wait = 0;
	cin >> wait;

	return 0;
}

ychooni 5년 전 1

거리가 같은 먹이들에 대한 우선순위가 있는데, 처리 하신건가요??

lswoo3021 5년 전 0

@ychooni 네ㅠㅡㅠ 94라인부터 117번까지가 우선순위 처리부분입니다... 저도 그게 의심스러워서

같은거리에 여러가지 놓고 테스트를 해봤는데 그 부분은 문제에서 주어진대로 잘 처리하고있었습니다

ychooni 5년 전 1

반례 드릴게요.

1 2 1 1 1 1

1 3 6 2 2 3

1 2 5 2 2 3

3 3 2 4 6 3

0 0 0 0 0 6

0 0 0 1 1 9

39 나와야 하는데, 37 나옵니다.

lswoo3021 5년 전 0

@ychooni 감사합니다!! 덕분에 문제점 찾아서 정답완료했네요 ㅠㅠ

원인은 .. 큰 물고기들로 인해 닿을수 없는 칸의 거리가 0으로 되어있어 제대로 돌지 않았네요...

그경우만 조건에 추가해주니 됐습니다 !! 감사합니다.

아 그리고 혹시 ㅠㅡㅠ 님께서는 문제 어떻게 푸셨는지 말씀해주실수 있을까요 !? ㅠㅡㅠ

저는 bfs 기초만 알면되는 줄 알았는데, 제가 푼 방법대로 하지 않으면 안되는 건가요 ?!

ychooni 5년 전 0

저는 좀 무식하게 풀어서 시간이 오래걸렸네요.

일달 먹을 수 있는 고기들 찾아서 저장해 놓고, 각각의 거리를 구한다음 정렬을 했어요.(거리에 따른 우선순위는 정렬 기준으로 처리)

그리고 가장 먼저 먹어야 하는 고기의 거리의 누적시키고, 현재 상어의 위치를 갱신하는 방식.

그리고 반복. N 제한이 워낙 작아서 시도했던 방법이긴 한데...

4ms 나오신거 보니깐, 저보다 훨씬 효율적으로 짜신거 같아요. (사실 코드가 너무 길어서 제대로 보진 않았습니다..ㅜ)

"맞은 사람"에서 0ms 로 통과하신 분들의 코드를 분석해보는게 더 도움이 될거 같습니다. :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 질문 및 알고리즘 질문드립니다.. !

lswoo3021 5년 전 1

ychooni 5년 전 1

lswoo3021 5년 전 0

ychooni 5년 전 1

lswoo3021 5년 전 0

ychooni 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말