백준 2178번 미로 탐색

풀기까지의 험난했던....

---

난 이걸 2일이나 걸려서 풀었다 ㅠ 

왜냐하면 이 역추적 부분 때문이다.

while (parent[y][x].x != x || parent[y][x].y != y) {
		cnt++;
		tPos = parent[y][x];
		y = tPos.y;
		x = tPos.x;
	}

아래는 원래 내가 썼던 코드이다..

while (parent[y][x].x != x || parent[y][x].y != y) {
		cnt++;
		y = parent[y][x].y;
		x = parent[y][x].x;
	}

parent[y][x].x를 할 때 y 값이 위와 같지 않기 때문에 이상한 출력이 나왔던 것이다.

 

근데 내가 집중이 안 되는 상황이었어서 그랬는지 이걸 어제와 오늘에 걸쳐 풀게 되었다.. ㅜ

 

주변이 시끄러워 집중이 잘 안 되는 것 같아서 헤드셋을 끼고 차분한 노래를 들으며 풀었더니 거의 바로 찾을 수 있었다.

무엇이든 나의 상태를 잘 확인하고, 인지하고 집중력이 높은 상태에서 해야 효율이 높아진다는 것을 다시 한 번 깨달았다... !ㅜ

 

백준 문제 2178번 미로 탐색

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct tagPos {
	int x;
	int y;
}Pos;

void EnQueue(Pos* q, Pos data, int* rear) {
	q[*rear] = data;
	(*rear)++;
}

Pos DeQueue(Pos* q, int* front) {
	return q[(*front)++];
}


int main() {

	int N, M;
	char** Matrix;
	char temp[101];

	scanf("%d %d", &N, &M);
	Matrix = (char**)malloc(sizeof(char*)*N);
	
	for (int i = 0; i < N; i++) {
		Matrix[i] = (char*)malloc(sizeof(char) * M+1);
		scanf("%s", temp);
		strcpy(Matrix[i], temp);
	}

	//BFS 후 역추적하며 횟수 셈

	Pos q_data[10001];
	int q_front = 0, q_rear = 0;//queue
	int nextX[] = { 0, 1, 0, -1 };
	int nextY[] = { 1, 0, -1, 0 };
	bool found[101][101] = {false,};
	Pos parent[101][101];
	Pos pos = {0, 0};
	Pos next;

	EnQueue(q_data, pos, &q_rear);
	found[pos.y][pos.x] = true;
	parent[pos.y][pos.x] = pos;

	//bfs
	while (q_front != q_rear) {
		pos = DeQueue(q_data, &q_front);

		//위, 오른, 아래, 왼 검사
		for (int i = 0; i < 4; i++) {
			next.x = pos.x+nextX[i];
			next.y = pos.y+nextY[i];

			if (next.x < 0 || next.y < 0 || next.x >= M || next.y >= N) { continue; }
			if (found[next.y][next.x]) { continue; }
			if (Matrix[next.y][next.x] == '0') { continue; }

			EnQueue(q_data, next, &q_rear);
			found[next.y][next.x] = true;
			parent[next.y][next.x] = pos;
		}
	}

	//역추적
	Pos tPos;
	int y = N - 1;
	int x = M - 1;
	int cnt = 0;
	while (parent[y][x].x != x || parent[y][x].y != y) {
		cnt++;
		tPos = parent[y][x];
		y = tPos.y;
		x = tPos.x;
	}
	if(parent[y][x].x == x && parent[y][x].y == y)
		cnt++;

	printf("%d", cnt);

	free(Matrix[0]);
	free(Matrix);

	return 0;
}

나의 코드이다. 

이번에도 좀 길게 짠듯하다.

다음에는 이런 문제를 1차원 배열로 풀어보고싶다!

 

후기

---

나의 상태를 잘 확인하고 보완하자!

 

홧팅!🤗