• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

선생님, 질문이 있습니다.

21.03.23 19:59 작성 조회수 109

0

선생님 강의 잘 듣고 있습니다!

선생님 3차원 배열을 통해 

공주 -> 산딸기 <- 기사

산딸기를 기점으로 최소거리를 합하는 방식으로 접근하셨군요

저는 그런데 다르게 풀어봤는데 어떤 점이 부족한지 잘 모르겠습니다. 

예제는 통과하는데

일단 답은 틀립니다!!

주석을 달아두었으니 보시는데 불편하지 않을 거라 생각합니다..

<저의 방식>

저는 일단 BFS를 2번 돌렸습니다. BFS1 BFS2

BFS1 : 공주의 위치에서 산딸기의 위치 정보를 모두 저장하기 위한 BFS

BFS2 : 산딸기의 위치에서 기사의 위치에 도달하기 위한 BFS

공주의 위치에서 산딸기의 위치에 도달하였을 때의 정보(x,y좌표, 이동 횟수)를 모두 배열에 저장합니다.

(기사를 지나치는 것에 제한을 두지 않고)

한번 BFS를 돌면 큐가 모두 비어있게 되니까 

배열에 저장되었던 모든 산딸기의 위치를 큐에 일괄적으로 넣고 다시 한 번 BFS를 돌려서

기사를 최초로 만나는 시점에 바로 bfs를 종료하도록 만들었습니다!!

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#define MAX 1001
using namespace std;


typedef struct node {
	int x;
	int y;
	int cnt = 0;
}Node;


int map[MAX][MAX];
bool visited[MAX][MAX];


int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
queue<Node> Q;
int strcnt = 0;
//vector<Node>strb[MAX];
Node strb[MAX];

int W, H;

Node start;




void BFS1() {

	Node current;
	while (!Q.empty()) {

		current.x = Q.front().x;
		current.y = Q.front().y;
		current.cnt = Q.front().cnt;
		Q.pop();
	//	printf("current // x : %d y : %d cnt : %d\n\n", current.x, current.y, current.cnt);
		if (map[current.x][current.y] == 4) {
			//printf("4 found!! // x :%d y : %d cnt : %d\n\n", current.x, current.y, current.cnt);
			strb[strcnt++] = current;
		}
		for (int i = 0; i < 4; i++) {

			int x = current.x + dx[i];
			int y = current.y + dy[i];

			if (x<1 || y<1 || x>H || y>W) { continue; }
			if (visited[x][y]) { continue; }
			if (map[x][y] == 1) { continue; }
			if ((!visited[x][y] && map[x][y] == 0) || (!visited[x][y] && map[x][y] == 3)||(!visited[x][y]&&map[x][y]==4)) {
				visited[x][y] = true;
				Node next;
				next.x = x;
				next.y = y;
				int nextcnt = current.cnt + 1;
				next.cnt = nextcnt;
				//printf("next // x : %d y : %d cnt : %d\n\n", next.x, next.y, next.cnt);
				Q.push(next);
			}
		}
	}



}
int mini = 100000;
void BFS2() {

	Node current;
	while (!Q.empty()) {

		current.x = Q.front().x;
		current.y = Q.front().y;
		current.cnt = Q.front().cnt;
		Q.pop();
		//printf("current // x : %d y : %d cnt : %d\n\n", current.x, current.y, current.cnt);
		if (map[current.x][current.y] == 3) {
			if (mini > current.cnt) {
				mini = current.cnt;
			}
		}

		for (int i = 0; i < 4; i++) {

			int x = current.x + dx[i];
			int y = current.y + dy[i];

			if (x<1 || y<1 || x>H || y>W) { continue; }
			if (visited[x][y]) { continue; }
			if (map[x][y] == 1) { continue; }
			if ((!visited[x][y] && map[x][y] == 0)||(!visited[x][y]&&map[x][y]==3)) {
				visited[x][y] = true;
				Node next;
				next.x = x;
				next.y = y;
				int nextcnt = current.cnt + 1;
				next.cnt = nextcnt;
				//printf("next // x : %d y : %d cnt : %d\n\n", next.x, next.y, next.cnt);
				Q.push(next);
			}
		}
	}



}


int main() {

	cin >> W >> H;

	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			int input;
			cin >> input;
			map[i][j]=input;
			if (input == 2) {
				start.x = i;
				start.y = j;
				start.cnt = 0;
			}
		}
	}

	Q.push(start);
	//printf("start // x : %d y : %d cnt : %d \n\n", start.x, start.y, start.cnt);
	visited[start.x][start.y] = true;
	BFS1();

	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			visited[i][j] = false;
		}
	}

	for (int i = 0; i < strcnt; i++) {
		Q.push(strb[i]);
		visited[strb[i].x][strb[i].y] = true;
	}

	//printf("<<<<BFS2 start>>>>\n\n");
	BFS2();

	printf("%d", mini);

}


답변 2

·

답변을 작성해보세요.

0

celestial_님의 프로필

celestial_

질문자

2021.03.24

아 선생님 알겠어요 혹시 제 방식대로 

4인 지점을 큐에 먼저 담아서 순차적으로 돌리면 방문을 한 곳을 다시 방문하지 못하기 때문에 문제가 생기는 군요  

예를 들어 우측 상단 4 4 4를 놓고 보면

가장 왼쪽에 있는 4가 지나간 지점을 가운데 4와 맨 오른쪽에 있는 4에서 출발하더라도

가장 왼쪽에 있는 4의 자취를 따라가지 못하기 때문에 절대 3으로 도달할 수 없는 거군요

제가 이해한 것이 맞을까요ㅕ?

0

안녕하세요^^

8 8

3 0 0 0 1 4 4 4

0 1 1 0 0 0 1 0

0 1 4 0 1 0 0 0

0 0 0 1 0 0 0 0

1 0 1 0 0 1 1 0

4 0 0 0 1 0 0 0

4 1 0 0 1 0 0 0

4 0 0 0 0 0 1 2

위에 입력으로 스스로 버그를 잡아 보세요. 답은 16입니다.

해결 못하면 잠시 접어두고 시간 날때 틈틈히 연구해 보세요. 스스로 해결해야 문제해결력이 늘어납니다.