[Baekjoon 10026] 적록색약
https://www.acmicpc.net/problem/10026
문제
const arr = []
const fs = require('fs');
const stdin = (process.platform === 'linux'
? fs.readFileSync('/dev/stdin').toString()
: `5
BBBBG
GRBBB
BBBBB
BBBBB
RRRRR
`
).split('\n');
const input = (() => {
let line = 0;
return () => stdin[line++];
})();
let t = input();
var n = t;
while (t--) {
arr.push(input().split(''))
}
//console.log(n, arr)
var dx = [-1, 1, 0, 0]
var dy = [0, 0, -1, 1]
function DFS(arr, x, y) {
visited[y][x] = true;
//console.log(y, x, arr[y][x], answer)
for (let k = 0; k < 4; k++) {
var nx = x + dx[k]
var ny = y + dy[k]
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
continue;
}
//console.log(...visited)
if (arr[ny][nx] === arr[y][x] && !visited[ny][nx]) {
//console.log('n', nx, ny, arr[ny][nx])
DFS(arr, nx, ny)
}
}
}
for (let k = 0; k < 2; k++) {
var visited = [];
for (let i = 0; i < n; i++) {
visited.push(new Array(arr.length).fill(false))
}
//console.log(visited)
var answer = 0;
if (k === 1) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (arr[j][i] === 'G') {
arr[j][i] = 'R'
}
}
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (visited[j][i] === false) {
answer++;
//console.log(...visited)
DFS(arr, i, j)
}
}
}
console.log(answer)
}문제풀이
input을 받고 arr에 다음과 같이 넣어준다.
var arr = [
['R', 'R', 'R', 'B', 'B'],
['G', 'G', 'B', 'B', 'B'],
['B', 'B', 'B', 'R', 'R'],
['B', 'B', 'R', 'R', 'R'],
['R', 'R', 'R', 'R', 'R']
]이와 마찬가지로 visited도 arr 요소의 개수만큼 만들어준다.
var visited = [
[false, false, false, false, false],
[false, false, false, false, false],
[false, false, false, false, false],
[false, false, false, false, false],
[false, false, false, false, false]
]여기까지가 기본적인 데이터 전처리 과정이다.
이제 이렇게 변환된 데이터를 DFS를 함수를 통해 답을 찾아주었다.
일반인/ 적록색약의 구분
경우는 크게 2가지로 나눌 수 있다.
경우 1. 일반인
R/G/B 모두를 개별적으로 구분 가능하다.
경우 2. 적록색약
(R,G)/B
R과 G를 같은 색으로 판단하기 대문에 2가지 색으로 구분이 가능하다.
이러한 부분은 if 문을 통해서 적록색약인 경우 'G' 값을 'R' 값으로 변환해 주었다.
DFS 과정
우선, 이 문제는 전체를 모두 탐색하는 것이기 때문에 DFS, BFS 어느 알고리즘으로 풀어도 동일한 값이 나온다.
dy, dx를 사용해 상하좌우로 현재 탐색 값을 이동시켜줬다.
이렇게 다음에 이동할 값이 (ex. x+dx) arr 내부 범위 안에 속해있으면서,
현재의 값과 동일한 값을 가지고 방문하지 않은 경우 다시 DFS를 돌려주었다.
[Baekjoon 1697] 숨바꼭질
https://www.acmicpc.net/problem/1697
문제
const sol = (input) => {
const [n, k] = input.split(" ").map(Number);
const visit = new Array(100001).fill(0);
function BFS(n) {
const queue = [];
queue.push([n, 0]);
visit[n] = 1;
while (queue.length) {
const [dot, depth] = queue.shift();
if (dot === k) return depth;
for (next of [dot - 1, dot + 1, dot * 2]) {
if (!visit[next] && next >= 0 && next <= 100000) {
visit[next] = 1;
queue.push([next, depth + 1]);
}
}
}
}
return BFS(n);
};
require("readline")
.createInterface(process.stdin, process.stdout)
.on("line", (line) => {
console.log(sol(line));
})
.on("close", () => {
process.exit();
});문제풀이
이 문제는 BFS로만 풀 수 있다.
그 이유는 동생을 만나는 가장 빠른 경우를 찾는 문제임과 동시에, DFS를 사용할 경우 무한한 깊이로 빠질 수 있기 때문이다.
간단한 예시로 5 17이 주어졌을 때,
5*2 17=>10*2 17=>20-1 17=>19-1 17=>18-1 17
이동 횟수: [5]
와 같은 방법이 가장 짧다고 생각할수도 있지만,
5*2 17=>10-1 17=>9*2 17=>18-1 17
이동 횟수: [4]
가 가장 짧다.
이러한 문제들은 BFS를 통해 접근하여 먼저 너비에 있는 요소들을 모두 검사하면서 확장해 나가는 것이 가장 좋은 방법이 된다.
visited?
문제를 풀면서 가장 고민했던 부분은 visited 처리를 어떻게 할 것인가? 에 대한 문제였다.
고민하다 문제 조건이 0~100000사이의 값으로 되어있어 이를 전체 길이로 하여 visited를 생성해 주었다.
depth는 어떻게 구하지
2번째로 많이 고민했던 부분은 BFS에서 depth를 어떻게 구할 것인지에 관한 부분이였는데,
이는 queue에 단순히 값만을 넣지 않고, depth와 함께 push해서 깊이를 구해주었다.
수빈이의 위치 이동하기
수빈이는
1. 걷는다(+1 또는 -1)
2. 순간이동한다.(x*2)
의 방법으로 이동할 수 있다. 따라서 이를 for..of 를 통해 순회시키며 queue에 [현재 위치, 이동 횟수]를 넣어주었다.
for (next of [dot - 1, dot + 1, dot * 2])
