[백준] JavaScript - 전쟁 - 전투(1303)

개요

문제 이름: 전쟁 - 전투 (1303)
문제 링크: https://www.acmicpc.net/problem/1303
플랫폼: 백준
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
소요 시간: 3시간

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 전쟁터에서 각 병사의 위치와 소속팀이 주어졌을 때, 각 팀의 전투력을 계산하는 문제입니다. 전투력은 같은 팀의 병사들이 인접해 있을 때 그 그룹의 크기의 제곱으로 계산됩니다. 이 문제는 그래프 탐색 알고리즘 중 하나인 DFS(Depth-First Search, 깊이 우선 탐색)를 사용하여 해결할 수 있습니다.

 

문제 해결을 위해 다음과 같은 접근 방식을 사용할 수 있습니다.

1. 전쟁터를 2차원 배열로 표현하고, 각 병사의 위치와 소속팀을 입력받습니다.
2. 전쟁터의 각 위치를 탐색하면서, 아직 방문하지 않은 병사의 위치에서 DFS를 시작합니다.
3. DFS를 통해 같은 팀의 인접한 병사들을 탐색하고, 그룹의 크기를 계산합니다.
4. 탐색이 끝나면 해당 그룹의 크기의 제곱을 해당 팀의 전투력에 더합니다.
5. 모든 위치를 탐색한 후, 각 팀의 총 전투력을 출력합니다.

DFS 알고리즘을 사용하여 같은 팀의 병사들을 탐색할 때, 상하좌우로 인접한 병사들만 고려합니다. 대각선 방향으로 인접한 병사들은 같은 그룹으로 간주하지 않습니다.

 

DFS 알고리즘

DFS는 그래프 탐색 알고리즘 중 하나로, 깊이 우선 탐색을 수행합니다. DFS는 한 노드에서 시작하여 인접한 노드를 먼저 탐색하고, 더 이상 탐색할 노드가 없으면 이전 노드로 돌아가는 과정을 반복합니다. 이 과정에서 스택(Stack)이나 재귀 호출을 사용하여 탐색 경로를 기록합니다.

DFS의 동작 과정은 다음과 같습니다.

1. 시작 노드를 스택에 넣고 방문 표시를 합니다.
2. 스택의 top에 있는 노드를 꺼내고, 그 노드의 인접한 노드 중 아직 방문하지 않은 노드를 스택에 넣고 방문 표시를 합니다.
3. 2번 과정을 더 이상 방문할 노드가 없을 때까지 반복합니다.
4. 스택이 비어있으면 탐색을 종료합니다.

DFS는 그래프의 모든 노드를 방문해야 할 때 유용하며, 경로 탐색, 연결 요소 찾기, 사이클 탐지 등의 문제를 해결하는 데 사용됩니다.

 

시도

1차 시도  (성공)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

// 첫 번째 줄에서 전쟁터의 크기를 가져옵니다.
const [n, m] = input[0].split(" ").map(Number);
// 나머지 줄은 전쟁터의 상태를 나타냅니다.
const battlefield = input.slice(1);

// 각 진영의 전력을 저장할 변수를 초기화합니다.
let whitePower = 0;
let bluePower = 0;

// 연결된 병사 그룹을 세는 재귀 함수입니다.
function countGroup(x, y, color) {
	// 경계를 벗어나거나 다른 색상이면 0을 반환합니다.
	if (x < 0 || x >= m || y < 0 || y >= n || battlefield[x][y] !== color) {
		return 0;
	}

	// 현재 위치의 병사를 세었음을 표시합니다. ('.'으로 변경)
	battlefield[x] = battlefield[x].substring(0, y) + "." + battlefield[x].substring(y + 1);

	// 현재 병사를 세고, 주변 병사들도 재귀적으로 셉니다.
	let count = 1;
	count += countGroup(x + 1, y, color); // 아래
	count += countGroup(x - 1, y, color); // 위
	count += countGroup(x, y + 1, color); // 오른쪽
	count += countGroup(x, y - 1, color); // 왼쪽

	return count;
}

// 전쟁터의 모든 위치를 순회합니다.
for (let i = 0; i < m; i++) {
	for (let j = 0; j < n; j++) {
		if (battlefield[i][j] === "W") {
			// 흰색 병사 그룹을 세고 전력을 계산합니다.
			const count = countGroup(i, j, "W");
			whitePower += count * count;
		} else if (battlefield[i][j] === "B") {
			// 파란색 병사 그룹을 세고 전력을 계산합니다.
			const count = countGroup(i, j, "B");
			bluePower += count * count;
		}
		// '.'은 이미 센 병사이므로 무시합니다.
	}
}

console.log(whitePower, bluePower);

 

위 코드는 DFS를 사용하여 문제를 해결한 것입니다. 주요 내용은 다음과 같습니다:

1. 입력 데이터를 읽어와 전쟁터의 크기(n, m)와 전쟁터 정보(battlefield)를 저장합니다.
2. 방문 여부를 저장하는 2차원 배열(visited)을 생성합니다.
3. 전쟁터의 각 위치를 탐색하면서, 아직 방문하지 않은 병사의 위치에서 DFS를 시작합니다.
4. DFS 함수(dfs)에서는 현재 위치의 병사와 같은 팀의 병사들을 상하좌우로 탐색하면서 그룹의 크기를 계산합니다.
5. 탐색이 끝나면 해당 그룹의 크기를 반환합니다.
6. 메인 함수에서는 DFS 결과를 받아 해당 팀의 전투력에 그룹 크기의 제곱을 더합니다.
7. 모든 위치를 탐색한 후, 각 팀의 총 전투력을 출력합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도:  O(n * m)
  • 전쟁터의 크기만큼 DFS 탐색을 수행합니다.
• 공간 복잡도: O(n * m)
  • 방문 여부를 저장하는 배열과 DFS 재귀 호출에 사용되는 스택 공간입니다.