인프런 커뮤니티 질문&답변

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

선생님 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);

}