[백준] JavaScript - 경로 찾기 (11403)

개요

 

문제 이름: 경로 찾기 (11403)
문제 링크: https://www.acmicpc.net/problem/11403
플랫폼: 백준
알고리즘 분류: DFS
소요 시간: 2시간

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 주어진 방향 그래프에서 모든 정점 쌍 (i, j)에 대해 i에서 j로 가는 경로가 있는지 판별하는 문제입니다. 이를 위해 DFS(깊이 우선 탐색) 알고리즘을 사용하여 각 정점에서 시작하여 도달 가능한 모든 정점을 탐색하고, 그 결과를 인접 행렬 형태로 저장합니다.

 

DFS는 그래프의 탐색 알고리즘 중 하나로, 시작 정점에서부터 한 방향으로 갈 수 있는 만큼 깊이 탐색하다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 계속 반복하여 모든 정점을 방문하는 순회 방법입니다.

 

이 문제에서는 각 정점에서 시작하는 DFS를 수행하여 해당 정점에서 도달 가능한 모든 정점을 찾습니다. 이때 도달 가능한 정점은 result 배열에 1로 표시합니다. 모든 정점에 대해 DFS를 수행하면 최종적으로 result 배열에는 모든 정점 쌍의 경로 존재 여부가 저장됩니다.

 

입력으로는 첫째 줄에 정점의 개수 N이 주어지고, 이어서 N개의 줄에 걸쳐 그래프의 인접 행렬이 주어집니다. 출력으로는 N개의 줄에 걸쳐 모든 정점 쌍의 경로 존재 여부를 0과 1로 표현한 인접 행렬 형태로 출력합니다.

 

즉, 주어진 가중치 없는 방향 그래프에서 모든 정점 쌍에 대해 한 정점에서 다른 정점으로 가는 경로가 존재하는지 여부를 판별하고, 그 결과를 인접 행렬 형식으로 출력하는 것이 목적입니다.

 

• 가중치 없는 방향 그래프 G가 주어집니다.
  • 첫째 줄에는 정점의 개수 N (1 ≤ N ≤ 100)이 주어집니다.
  • 둘째 줄부터 N개의 줄에는 그래프의 인접 행렬이 주어집니다.
  • i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻입니다.
  • i번째 줄의 i번째 숫자는 항상 0입니다.
• 모든 정점 쌍 (i, j)에 대해서 다음을 판별해야 합니다.
  • i에서 j로 가는 경로가 있는지 여부를 판별합니다.
  • 경로의 길이는 0보다 커야 합니다.
• 출력으로는 총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력해야 합니다.
  • 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로 출력합니다.
  • 정점 i에서 j로 가는 경로가 없으면 i번째 줄의 j번째 숫자를 0으로 출력합니다.

문제 요구사항은 위와 같습니다.

 

1. 입력 처리
   1. fs 모듈을 사용하여 입력을 읽어오고, 첫째 줄에서 정점의 개수 N을 파싱하고, 이어지는 N개의 줄에서 그래프의 인접 행렬을 2차원 배열 graph에 저장합니다.
2. 결과 배열 초기화
   1. 결과를 저장할 N x N 크기의 2차원 배열 result를 생성하고 모든 원소를 0으로 초기화합니다.
3. DFS 함수 정의
   1. [start: DFS를 시작하는 정점의 번호]
      [current: 현재 탐색 중인 정점의 번호]
      [visited: 각 정점의 방문 여부를 저장하는 배열]
   2. dfs 함수를 정의하여 그래프를 탐색합니다.
   3. dfs 함수는 현재 정점 current에서 시작하여 인접한 모든 정점을 탐색합니다.
   4. 만약 current에서 next로 가는 간선이 존재하고(graph[current][next] === 1), 아직 next를 방문하지 않았다면(!visited[next]), result[start][next]를 1로 설정하여 start에서 next로 가는 경로가 존재함을 표시하고, next를 방문 처리한 후 next에서 다시 dfs를 재귀적으로 호출합니다.
4. 모든 정점에 대해 DFS 수행
   1. 모든 정점 i에 대해 DFS를 수행합니다.
   2. 각 정점에서 시작할 때마다 새로운 방문 배열 visited를 생성하고, i번 정점에서 시작하는 DFS를 호출합니다.
5. 결과 출력
   1. result 배열을 인접 행렬 형태로 출력합니다.
   2. 각 행의 원소를 공백으로 구분하여 문자열로 만들고, 이를 outputLines 배열에 저장한 후, 최종적으로 outputLines의 모든 문자열을 줄바꿈 문자로 구분하여 출력합니다.

풀이 방식은 위와 같습니다.

 

시도

1차 시도  (성공)

// fs 모듈을 불러와서 입력을 받습니다.
const fs = require("fs");
// 입력값을 읽어와서 줄바꿈으로 분리합니다.
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// 첫 번째 줄에서 정점의 개수 N을 읽습니다.
const N = parseInt(input[0]);
// 두 번째 줄부터 N개의 줄을 읽어 인접 행렬을 만듭니다.
// 각 줄을 공백으로 분리하고 숫자로 변환합니다.
const graph = input.slice(1).map((line) => line.split(" ").map(Number));

// === 여기까지가 입력 부분 ===

// N x N 크기의 2차원 배열을 만들고 0으로 초기화합니다.
// Array.from()은 새 배열을 생성하는 메소드입니다.
// {length: N}은 길이가 N인 배열을 만들고,
// () => Array(N).fill(0)는 각 원소를 길이 N의 0으로 채워진 배열로 만듭니다.
const result = Array.from({ length: N }, () => Array(N).fill(0));

/**
 * DFS(깊이 우선 탐색)를 수행하는 함수
 * start - 시작 정점 번호
 * current - 현재 정점 번호
 * visited - 방문 여부를 저장하는 배열
 */
function dfs(start, current, visited) {
	// 현재 정점에서 갈 수 있는 모든 정점을 확인합니다.
	for (let next = 0; next < N; next++) {
		// graph[current][next] === 1: 현재 정점에서 다음 정점으로 가는 경로가 있음
		// !visited[next]: 다음 정점을 아직 방문하지 않았음
		if (graph[current][next] && !visited[next]) {
			// start에서 next로 가는 경로가 있다는 것을 표시합니다.
			result[start][next] = 1;
			// next 정점을 방문했다고 표시합니다.
			visited[next] = true;
			// next 정점에서 다시 DFS를 수행합니다.
			dfs(start, next, visited);
		}
	}
}

// 모든 정점에 대해 DFS를 수행합니다.
for (let i = 0; i < N; i++) {
	// 각 정점에서 시작할 때마다 새로운 방문 배열을 만듭니다.
	const visited = Array(N).fill(false);
	// i번 정점에서 시작하는 DFS를 수행합니다.
	dfs(i, i, visited);
}

// === 결과 출력 부분 ===
// 각 줄의 결과를 저장할 배열을 생성합니다.
let outputLines = [];

// result 배열의 각 행을 처리합니다.
for (let i = 0; i < N; i++) {
	// result[i]는 현재 처리할 행입니다.
	// join(' ')은 배열의 각 원소를 공백으로 구분하여 하나의 문자열로 만듭니다.
	// 예: [1, 0, 1]  →  "1 0 1"
	let currentLine = result[i].join(" ");

	// 만든 문자열을 outputLines 배열에 추가합니다.
	outputLines.push(currentLine);
}

// outputLines 배열의 모든 원소를 줄바꿈 문자(\n)로 구분하여 하나의 문자열로 만들고 출력합니다.
// 예: ["1 1 1", "1 1 1", "1 1 1"]  →  "1 1 1\n1 1 1\n1 1 1"
console.log(outputLines.join("\n"));

이 코드는 DFS를 사용하여 모든 정점 쌍 사이의 경로 존재 여부를 판별하고, 결과를 인접 행렬 형태로 출력합니다.

 

먼저 입력을 받아와서 첫째 줄에서 정점의 개수 N을 읽고, 이후 N개의 줄에서 그래프의 인접 행렬을 2차원 배열 graph에 저장합니다.

 

그 다음 결과를 저장할 N x N 크기의 2차원 배열 result를 생성하고 모든 원소를 0으로 초기화합니다. Array.from()과 fill() 메서드를 사용하여 간결하게 초기화를 수행합니다.

 

dfs 함수는 DFS 알고리즘을 구현한 것으로, 현재 정점 current에서 시작하여 인접한 모든 정점을 탐색합니다. 만약 current에서 next로 가는 간선이 존재하고 아직 next를 방문하지 않았다면, result 배열에 해당 경로를 표시하고 next를 방문 처리한 후 next에서 다시 dfs를 재귀적으로 호출합니다.

 

모든 정점에 대해 DFS를 수행하는 부분에서는 각 정점 i에서 시작하는 DFS를 수행합니다. 이때 각 정점에서 시작할 때마다 새로운 방문 배열 visited를 생성하여 사용합니다.

 

마지막으로 결과를 출력하기 위해 result 배열의 각 행을 문자열로 변환하여 outputLines 배열에 저장하고, 이를 줄바꿈 문자로 구분하여 최종 출력을 생성합니다.

 

사용된 주요 메서드

• Array.from(arrayLike[, mapFn[, thisArg]]): 유사 배열 객체나 반복 가능한 객체로부터 새로운 Array 인스턴스를 생성합니다. arrayLike는 배열로 변환할 객체이고, mapFn은 배열의 각 요소에 대해 호출할 맵핑 함수, thisArg는 mapFn 실행 시에 this로 사용할 값입니다.
• Array.prototype.slice([begin[, end]]): 배열의 begin부터 end까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환합니다. 원본 배열은 바뀌지 않습니다.
• Array.prototype.map(callback(currentValue[, index[, array]])[, thisArg]): 배열 내의 모든 요소 각각에 대하여 주어진 함수(callback)를 호출한 결과를 모아 새로운 배열을 반환합니다.
• Array.prototype.fill(value[, start[, end]]): 배열의 start 인덱스부터 end 인덱스의 이전까지 정적인 값 하나로 채웁니다. start와 end는 선택 사항이며, 기본 값은 각각 0과 this 객체의 length 입니다.
• Array.prototype.join([separator]): 배열의 모든 요소를 연결해 하나의 문자열로 만듭니다. separator는 요소를 구분할 문자열을 지정하며, 생략하면 쉼표를 사용합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(n^3)
  • 모든 정점에 대해 DFS를 수행하고, 각 DFS마다 인접한 모든 정점을 탐색하므로 O(n^2)의 시간이 소요됩니다.
  • 그리고 결과를 출력하는 부분에서 각 행을 문자열로 변환하는 데에도 O(n)의 시간이 소요되므로, 총 시간 복잡도는 O(n^3)이 됩니다.
• 공간 복잡도: O(n^2)
  • 입력으로 주어진 그래프의 인접 행렬을 저장하는 graph 배열과 결과를 저장하는 result 배열이 각각 n x n 크기를 가지므로 O(n^2)의 공간이 필요합니다.
  • 그 외에 방문 배열 visited와 결과 출력을 위한 outputLines 배열이 있지만, 이들은 모두 O(n)의 공간만을 차지하므로 전체 공간 복잡도에는 영향을 주지 않습니다.