나름 잘 짰다고 생각했는데 ㅠㅠ

미로찾기 코드인데 상하좌우로만 움직이는게 아니라 대각선으로도 움직을수 있고 상하좌우는 행동력1,대각선은 행동력2라고 하고 행동력이 가장적은 길이 몇개있나를 리턴하는 함수입니다.
초반에는 제가생각한대로 가다가 어느 한지점에서 무슨문제인지 조건이 맞는데도 그조건으로 안들어오는거 같습니다.
이 부분은 코드에 주석으로 표시해 두었습니다.
생각대로 되다가 안되니 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
왜이런지 아시는분 가르쳐주세요ㅠㅠ
1은 벽이고 0은 길입니다.대각선이동가능(행동력2),상하좌우(행동력1)

#include <stdio.h>
#define N 0
#define NE 1
#define E 2
#define SE 3
#define S 4
#define SW 5
#define W 6
#define NW 7

typedef struct _Infor {
	int x;
	int y;
}Infor;

int move(int(*maze)[7], int(*mark)[7], int row, int col, Infor* stack, int* top) {//미로,갔던길체크,세로배열크기,가로배열크기,현재있는 위치,이동비용
	static int min = 999999999, count = 0;//이동비용 최소인 경로 갯수
	int R;
	for (R = 0; R < 8; R++) {//8방향 탐색
		if (stack->x == row - 2 && stack->y == col - 2 && R == 7) {//출구도착하면,8번중에1번
			if (min >= *top) {
				count++;
				if (min > *top) {
					count = 1;
					min = *top;
				}
			}
		}
		
		switch (R)//0~7까지 차례대로 북부터~동~남~서~북남까지 확인
		{
		case N:
			if (maze[stack->x - 1][stack->y] == 0 && mark[stack->x - 1][stack->y] == 0) {
				stack->x -= 1;//이동
				mark[stack->x][stack->y] = 1;//이동표시
				*top += 1;//이동비용증가
				move(maze, mark, row, col, stack, top);//다시 8방향 확인위해호출(재귀)
			}
			break;
		case NE:

			if (maze[stack->x - 1][stack->y + 1] == 0 && mark[stack->x - 1][stack->y + 1] == 0) {
				stack->x -= 1;
				stack->y += 1;
				mark[stack->x][stack->y] = 1;
				*top += 2;
				move(maze, mark, row, col, stack, top);
			}
			break;
		case E:
			if (maze[stack->x][stack->y + 1] == 0 && mark[stack->x][stack->y + 1] == 0) {
				stack->y += 1;
				mark[stack->x][stack->y] = 1;
				*top += 1;
				
				move(maze, mark, row, col, stack, top);
			}
			break;
		case SE:
			if (maze[stack->x + 1][stack->y + 1] == 0 && mark[stack->x + 1][stack->y + 1] == 0) {
				stack->x += 1;
				stack->y += 1;
				mark[stack->x][stack->y] = 1;
				*top += 2;
				
				move(maze, mark, row, col, stack, top);
			}
			break;
		case S:
			if (maze[stack->x + 1][stack->y] == 0 && mark[stack->x + 1][stack->y] == 0) {
				stack->x += 1;
				mark[stack->x][stack->y] = 1;
				*top += 1;
				
				move(maze, mark, row, col, stack, top);
			}
			break;
		case SW:
			if (maze[stack->x + 1][stack->y - 1] == 0 && mark[stack->x + 1][stack->y - 1] == 0) {
				stack->x += 1;
				stack->y -= 1;
				mark[stack->x][stack->y] = 1;
				*top += 2;
				
				move(maze, mark, row, col, stack, top);
			}
			break;
		case W:
			if (maze[stack->x][stack->y - 1] == 0 && mark[stack->x][stack->y - 1] == 0) {
				stack->y -= 1;
				mark[stack->x][stack->y] = 1;
				*top += 1;
				//printf("%d\n", *top);  <--------이부분부터 잘못된거 같습니다. 로직대로 따라가보면 *top값이 8이 나와야하는데 여기서부터 안나오네요ㅠㅠ
				move(maze, mark, row, col, stack, top);
			}
			break;
		case NW:
			if (maze[stack->x - 1][stack->y - 1] == 0 && mark[stack->x - 1][stack->y - 1] == 0) {
				stack->x -= 1;
				stack->y -= 1;
				mark[stack->x][stack->y] = 1;
				*top += 2;
				
				move(maze, mark, row, col, stack, top);
				
			}
			break;
		default:
			printf("switch문 오류");
		}

	}
	return count;
}

int main() {
	Infor mamory;

	int* top;
	int num1 = 0;
	top = &num1;

	int Maze[7][7] = {//1은벽,0은 길
		{1,1,1,1,1,1,1},
		{1,0,0,0,0,1,1},
		{1,1,1,0,1,1,1},
		{1,1,0,0,0,0,1},
		{1,1,0,1,1,1,1},
		{1,1,0,0,0,0,1},
		{1,1,1,1,1,1,1},
	};

	int Mark[7][7] = {
		{0,0,0,0,0,0,0},
		{0,1,0,0,0,0,0},
		{0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0}
	};

	mamory.x = 1;
	mamory.y = 1;
	int solution;

	solution = move(Maze, Mark, 7, 7, &mamory, top);
	
	printf("%d개", solution);
}

먼저 의아한 점

  Infor mamory;
  ...
  solution = move(Maze, Mark, 7, 7, &mamory, top); 
/* mamory는 1개의 Infor만 저장할 수 있으므로 stack이 아닙니다.
   경로를 출력 하는게 아니니 stack이 필요한 문제는 아니지만,
   main 함수가 문제의 일부라면 왜 이렇게 문제를 구성 하셨는지 의도를 파악하기 힘드네요. */

로직 문제 부분

if (stack->x == row - 2 && stack->y == col - 2 && R == 7)
/* for 문 밖에서 진행하세요. for 안에서 돌릴 이유가 없습니다.
   R == 7 은 불필요한 조건이 되겠죠.
   바로 return 시키거나 for 문을 진행하지 않도록 조건을 주세요.*/
if (maze[stack->x - 1][stack->y] == 0 && mark[stack->x - 1][stack->y] == 0) {
  stack->x -= 1;
  mark[stack->x][stack->y] = 1;
  *top += 1;
  move(maze, mark, row, col, stack, top);
  /* 이동 후 stack, mark와 top를 다시 원복을 시키는 코드가 없습니다.
     이러면 금방 mark가 다 1로 채워져서 이동 할 수 없고, top는 무한이 증가만 하겠죠? 
     아마 주석 부분에서 멈춰있는 이유는 8면의 mark가 모두 1로 차있기 때문일겁니다.
     stack 돌려 놓으셔야 move에서 나오고 다음 방향을 다시 자기 자리 기준에서 진행하겠죠?*/
}

코드 리뷰

#define N 0
#define NE 1
#define E 2
#define SE 3
#define S 4
#define SW 5
#define W 6
#define NW 7

/* 1. enum 으로 바꿔보세요. 
   2. N, S 와 같은 겹치기 쉬운 naming은 좋지않습니다. 이름을 붙일 때 의미을 짐작 할 수 있어야 합니다.
      길더라도 DIRECTION_N // DIRECTION_NORTH 와 같이 만들어주세요. */
  int R;
  for (R = 0; R < 8; R++) {
/* 위는 C89 implementation 입니다. 요즘 컴파일러에서 유의미한 성능 차이는 없습니다.
   교수님이 좋아하신다거나... 특별한 이유가 있는게 아니라면 가독성을 저하합니다. */

Test Code
#include <chrono>
#include <iostream>
#include <string>

#define MAX_COUNT 10000

template<typename Function, typename ...Params>
void PrintExecutionTime(std::string name, Function function, Params&&... params) {
  auto start = std::chrono::high_resolution_clock::now();
  function(std::forward<Params>(params)...);
  auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(
      std::chrono::high_resolution_clock::now() - start);
  std::cout << name << ": "<< duration.count() << " ms" << std::endl;
}

int main(int argc, char** argv)
{
  PrintExecutionTime("int declaration before for loop", []() {
    int i;
    for(i = 0; i < MAX_COUNT; ++i) {
      int j;
      for (j = 0; j < MAX_COUNT; ++j);
    }
  });

  PrintExecutionTime("int declaration at for loop", []() {
    for(int i = 0; i < MAX_COUNT; ++i) {
      for (int j = 0; j < MAX_COUNT; ++j);
    }
  });

  return 0;
}
Test Result
$ g++ main.cpp && ./a.out
int declaration before for loop: 147 ms
int declaration at for loop: 148 ms
if (min >= *top) {
  count++;
  if (min > *top) {
    count = 1;
    min = *top;
  }
}
/* min > *top 와 min == *top 로 if .. else if .. 구문을 사용하여 나누어 주세요.
   - min > *top 시에 의미 없는 count++이 실행됩니다.
   - min == *top 시에 의미 없는 의미 없이 비교문을 한 번 더 실행됩니다. 
   - 가독성을 저해합니다. */

제가 너무 쉽게 생각한거 같네요…
재귀처럼 쓰면 아무것도 해당하상이 없을때 되돌아 가는줄 알았네요…ㅠㅠ
아래 테스트 코드도 써주셨는데 제 실력으론 어림도 없는거 같습니다…ㅠㅠ
그래도 좋은 지적 감사합니다 다시 해볼게요~

1 Like

베이스 코드를 충분히 생각해서 잘 짜셨어요.
아마 고쳐보시는 도중에, 충분히 습득하실 것 같습니다 :slight_smile:

테스트는 코드는 알맹이만 보세요.
PrintExecutionTime 함수는 main문 안에 있는 두가지 함수를 실행시키고 시간을 측정하는 코드입니다.
아직 이해하실 필요는 없어요.
int 선언이 for 문 밖이던 안이던 ±1ms 정도 오차로 의미 없다는 뜻이죠.

1 Like
#include <stdio.h>

const int r[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int c[8] = { 0, -1, 0, 1, -1, 1, 1, -1 };
const int dest = 5, done = -1, empty = 0, wall = 1;

int Maze[7][7] = {  //1은벽,0은 길
	{1,1,1,1,1,1,1},
	{1,0,0,0,0,1,1},
	{1,1,1,0,1,1,1},
	{1,1,0,0,0,0,1},
	{1,1,0,1,1,1,1},
	{1,1,0,0,0,0,1},
	{1,1,1,1,1,1,1},
};

int move(int curr_r, int curr_c, int cost) {
	if (curr_r == dest && curr_c == dest) {
		printf("cost: %d\n", cost);
		return 1;
	}

	int res = 0;

	for (int i = 0; i < 8; ++i) {
		if (Maze[curr_r + r[i]][curr_c + c[i]] == empty) {
			Maze[curr_r + r[i]][curr_c + c[i]] = done;
			res = move(curr_r + r[i], curr_c + c[i], cost + i / 4 + 1);
			if (res) break;
		}
	}
	return res;
}

int main() {
	int curr_r = 1, curr_c = 1;
	move(curr_r, curr_c, 0);
}

이런식으로 재귀로 구현하시면 될거같습니다.

스택으로 구현하실때는요, 재귀하지말고 push pop을 하면 되는데요.
재귀할때 함수를 call, return하는걸 push pop으로 바꿔서 하시면됩니다.

1 Like

넘나 상냥한 답변들이신 것.

이건 제 개인적인 생각일 뿐이긴 하지만,

여기 찾아와주시는 분들께 상냥하게 대접해야 저희 커뮤니티 이미지도 좋아지고
뭐 그런 긍정적인 영향이 좀 생기지 않을까. 그렇게 생각해서요. ㅎㅎㅎㅎ

물론 날먹하려는 사람들을 보면 좀 괘씸할때도 있지만,

제가 답변을 어떻게 하든
열심히 공부하는 사람은 무언가를 얻으려고 노력할거고,
그렇지 않은 사람은 아무리 노력하라 해도 하지않기에…

저는 그저 저만의 최선의 답을 드리고자할뿐이고,
그게 노력하는 사람들께 조금이라도 도움이 되었으면 좋겠다는 생각뿐입니다. ㅎㅎㅎ

5 Likes