[Softeer] [HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기 _ C++

이얀조·2023년 10월 3일

🎞Softeer

목록 보기

2/2

[HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기

🧪 문제

Sam은 팀장님으로부터 차량이 이동 가능한 시나리오의 수를 찾으라는 업무 지시를 받았습니다. 
이동은 숫자 0과 1로만 이루어져 있는 n x n 크기의 격자 위에서 일어납니다. 
숫자 0은 빈 칸을 의미하며, 숫자 1은 해당 칸이 벽으로 막혀 있음을 의미합니다. 
아래는 n이 3인 경우의 예시입니다.
0 0 0
0 0 0
0 0 1
차량은 n x n 격자 내에서 m개의 지점을 순서대로 방문하려고 합니다. 
이 때 이동은 항상 상하좌우 중 인접한 칸으로만 이동하되 벽은 지나갈 수 없으며, 한 번 지났던 지점은 다시는 방문해서는 안 됩니다. 
이러한 조건 하에서 차량이 이동 가능한 서로 다른 가지 수를 구하는 프로그램을 작성해보세요.
방문해야 하는 지점의 첫 지점이 출발점이며, 마지막 지점이 도착점임에 유의합니다.
위의 예에서 m = 3, 방문해야 하는 지점이 순서대로 (3행, 1열), (1행, 2열), (2행, 3열)이라면, 다음과 같이 5가지의 시나리오가 가능합니다.

(3행, 1열) → (3행, 2열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)
(3행, 1열) → (3행, 2열) → (2행, 2열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)
(3행, 1열) → (2행, 1열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)
(3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)
(3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (2행, 2열) → (2행, 3열)

🦯 코드

[C++]

#include<iostream>
#include<vector>

using namespace std;

struct DIR {
	int y;
	int x;
};

vector<DIR> dir;
void dfs(int* result, vector<vector<int> >* ck_map, vector<vector<int> > map, vector<DIR> points, DIR now, int point_num);
int main(int argc, char** argv)
{
	int n, m;
	vector<vector<int> > map, ckmap;
	vector<DIR> points;

	cin >> n >> m;

	// init dir
	dir.push_back({-1, 0});
	dir.push_back({0, 1});
	dir.push_back({1, 0});
	dir.push_back({0, -1});

	// init map
	for (int i = 0; i < n; i++) {
		vector<int> v_tmp, ckv_tmp;

		for (int j = 0; j < n; j++) {
			int tmp;
			cin >> tmp;

			v_tmp.push_back(tmp);
			ckv_tmp.push_back(tmp);
		}

		map.push_back(v_tmp);
		ckmap.push_back(ckv_tmp);
	}

	// init points
	for (int i = 0; i < m; i++) {
		int y, x;

		cin >> y >> x;
		map[y - 1][x - 1] = -1;
		points.push_back({y - 1, x - 1});
	}

	int result = 0;
	dfs(&result, &ckmap, map, points, points[0], 0);
	cout << result << endl;
	return 0;
}

void dfs(int* result, vector<vector<int> >* CK_MAP, vector<vector<int> > map, vector<DIR> points, DIR now, int point_num) {
	vector<vector<int> > ck_map = *CK_MAP;
	
	if (map[now.y][now.x] < 0 && (now.y == points[point_num].y && now.x == points[point_num].x)) {
		if (point_num == points.size() - 1) {
			result[0] += 1;		
			return;
		}
		else {
			ck_map[now.y][now.x] = 1;
			dfs(result, &ck_map, map, points, now, point_num + 1);
			ck_map[now.y][now.x] = 0;
		}
	}
	else {
		for (int i = 0; i < 4; i++) {
			int next_y = now.y + dir[i].y, next_x = now.x + dir[i].x;

			if ((next_y < map.size() && next_y >= 0) && (next_x < map.size() && next_x >= 0)) {
				if (ck_map[next_y][next_x] == 0 && map[next_y][next_x] <= 0) {
					ck_map[next_y][next_x] = 1;
					dfs(result, &ck_map, map, points, {next_y, next_x}, point_num);
					ck_map[next_y][next_x] = 0;
				}
			}
		}
	}
}

[C(미완)]

#include <stdio.h>
#include <stdlib.h>

struct DIR {
    int y;
    int x;
};

struct DIR dir[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
void dfs(int *result, int **map, int ***CKMAP, struct DIR *points, struct DIR now, int point_num, int size);
int main(void)
{
    int n, m;
    int **map, **ckmap;
    struct DIR *points;

    scanf("%d %d", &n, &m);
    map = (int**)malloc(sizeof(int*) * n);
    ckmap = (int**)malloc(sizeof(int*) * n);
    points = (struct DIR*)malloc(sizeof(struct DIR) * m);

    // init map
    for (int i = 0; i < n; i++) {
        int* m_tmp = (int*)malloc(sizeof(int) * n);
        int* ckm_tmp = (int*)malloc(sizeof(int) * n);

        for (int j = 0; j < n; j++) {
            int tmp;
            scanf("%d", &tmp);
            m_tmp[j] = tmp;
            ckm_tmp[j] = tmp;
        }
        map[i] = m_tmp;
        ckmap[i] = ckm_tmp;
    }

    // init points
    for (int i = 0; i < m; i++) {
        int tmp_y, tmp_x;
        scanf("%d %d", &tmp_y, &tmp_x);

        points[i].y = tmp_y - 1; points[i].x = tmp_x - 1;
        map[tmp_y - 1][tmp_x - 1] = -1;
    }

    int result = 0;
    dfs(&result, map, &ckmap, points, points[0], 0, n);
    printf("%d\n", result);

    // Free allocated memory
    for (int i = 0; i < n; i++) {
        free(map[i]);
        free(ckmap[i]);
    }
    free(map);
    free(ckmap);
    free(points);

    return 0;
}

void dfs(int *result, int **map, int ***CKMAP, struct DIR *points, struct DIR now, int point_num, int size)
{
    int **ck_map = *CKMAP;

    if (map[now.y][now.x] < 0 && (points[point_num].y == now.y && points[point_num].x == now.x)) {
        if (point_num == size - 1) {
            result[0] += 1;
            return;
        }
        else {
            ck_map[now.y][now.x] = 1;
            dfs(result, map, &ck_map, points, now, point_num + 1, size);
            ck_map[now.y][now.x] = 0;
        }
    }
    else {
        for (int i = 0; i < 4; i++) {
            int next_y = now.y + dir[i].y, next_x = now.x + dir[i].x;

            if ((next_y < size && next_y > -1) && (next_x < size && next_x > -1)) {
                if (ck_map[next_y][next_x] == 0 && map[next_y][next_x] < 1) {
                    struct DIR next = {next_y, next_x};

                    ck_map[next_y][next_x] = 1;
                    dfs(result, map, &ck_map, points, next, point_num, size);
                    ck_map[next_y][next_x] = 0;
                }
            }
        }
    }
}

📌 풀이

이 문제는 DFS 로 탐색을 진행하는 문제이다. (특히 백트래킹의 기초)
여기서 내가 중요하게 짚고 넘어가려 했던것은 다음과 같다.

순서대로 목표지점에 도달할 것

따라서 나는 각 목표지점을 points 라는 배열에 할당했다.

이후 dfs 를 돌고, 목표하는 다음지점의 points 배열 idx를 함께 넣어줬다.
→ 당연히 맨 처음 지점은 dfs 함수에 들어가자마자 다음 목표 지점의 idx 번호를 넘겨주고 차례를 넘긴다.

현재 차례(point_num) 이 마지막 목표지점의 차례이면서, 현재 위치가 목표지점의 위치라면 종료하기 위해 return 을 호출, result 의 크기를 1 키워준다.

💤 어려웠던 점

백트래킹과정에서 목표지점의 방문 여부를 체크하지 않아서 원하는 답이 나오지 않았다.
분명 C++ 과 동일하게 C 를 짠 것 같은데 C로 문제를 돌리면 틀렸습니다가 나온다 . . ㅠ

이얀조

이얀조다!

이전 포스트