백준(BOJ) 11403번 경로찾기

안녕하세요? 오늘은 백준 알고리즘 사이트에 있는 문제 중 11403번 경로찾기 문제를 풀어보겠습니다.

문제부터 보시겠습니다.

i에서 j로 가는 경로가 있으면 1, 없으면 0을 저장하고 모두 출력하는 문제입니다.

정점의 인덱스가 0부터 시작한다고 가정하고 예제 입력1을 보시면 i가 0일 때, 1로 갈 수 있고 i가 1일 때, 2로 갈 수 있고, i가 2일 떄, 0으로 갈 수 있습니다.

즉 i가 0일 때, 0, 1, 2 모두 갈 수 있습니다.

마찬가지로 나머지 행까지 모두 계산하면 예제 출력 1과 같은 맵을 얻을 수 있습니다.

저는 이 문제를 DFS 알고리즘을 사용하여 풀었습니다. 갈 수 있는 정점을 모두 들리고 다시 원점으로 돌아오면 탐색이 종료되도록 구현하였습니다.

다시 원점으로 돌아온다는 개념을 visited라는 bool타입 2차원 변수를 사용하여 구현하였습니다. 

그림을 통해 설명하겠습니다.

먼저 예제 입력1에서 다음과 같은 visited 맵이 구성됩니다.

이런 상태로 별도의 장치를 안하면

0에서 1, 1에서2, 2에서 0, 다시 0에서 1, 1에서 2, 2에서 0을 무한 반복해버리고

재귀함수이기 때문에 언젠가 stack 메모리의 자원이 고갈될 것입니다.

따라서 이미 다녀온 지점은 True로 설정하여 또 다시 같은 곳을 반복하지 않도록 제어 장치를 마련하였습니다.

자 그럼 이제 소스코드를 보시죠!

#include <iostream>
#include <cstring>
#define MAP_SIZE 101

int map[MAP_SIZE][MAP_SIZE];
int ans[MAP_SIZE][MAP_SIZE];
bool visited[MAP_SIZE][MAP_SIZE];
int N;

void input();
void DFS(int target, int r);
void output();

int main() {
	input();
	for (int r = 0; r < N; r++) {
		memset(visited, false, sizeof(visited));
		DFS(r, r);
	}
	output();
	return 0;
}

void input() {
	std::cin >> N;
	for (int r = 0; r <N; r++) {
		for (int c = 0; c < N; c++) {
			std::cin >> map[r][c];
		}
	}
}

void DFS(int target, int r) {
	for (int c = 0; c < N; c++) {
		if (map[r][c] == 1 && visited[r][c] == false) {
			ans[target][c] = 1;
			visited[r][c] = true;
			DFS(target, c);
		}
	}
}

void output() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			std::cout << ans[r][c] << ' ';
		}
		std::cout << std::endl;
	}
}

input() 함수에서는 입력을 받고 output() 함수에선 정답을 출력하도록 하였습니다.

그리고 DFS()함수를 사용하여 탐색을 진행하였습니다. 

DFS()함수를 호출할 때, target이라는 매개변수를 사용하였는데, 이는 현재 target으로 하고 있는 정점의 인덱스가 변하지 않도록 하기 위함입니다.

전 이 문제를 인접행렬을 사용하여 풀었으나 인접리스트를 사용할 시, 훨씬 더 효율적으로 문제를 풀어낼 수 있습니다.

그리고 가급적이면 인접리스트로 풀 수 있는 문제는 인접리스트를 사용하여 풀려고 하는 것이 더 좋은 접근 방식이라고 생각합니다.

감사합니다.