반응형
문제 출처
https://www.acmicpc.net/problem/16724
정답 풀이
아래 그림과 같이 화살표를 무작위로 그려봤을 때,
dfs로 탐색을 해서 해당 연결이 끝나는 곳에 safe zone을 두면 되겠다는 아이디어가 떠오른다.
그런데,
visited 방문 처리로만 safe zone 을 다루면 안된다.
왜냐하면 파란색 애들은 이미 방문 처리로 끝나고, 주황색 애들이 남아버린다.
원래 같은 한 묶음이 될 수 있는데 !
어떻게 위와 같은 경우에도 한 묶음으로 만들 수 있을까?
- dfs 반복문을 통해 사이클을 다 돈다.
=> visited[x][y] = 2 로 처리해둔다.
- 또 아직 방문하지 않은 곳 dfs 반복문으로 돈다.
=> 현재 돌고 있는 곳은 1로 처리,
=> 1로 처리하다가 만약 자기 자신이 cycle에 있는 좌표를 만난다면,
=> 새로운 safeZone +1 이다.
- 만약 2를 만난다면
=> 기존 safeZone 에 편입되는 것이니, dfs 탐색을 그대로 중단한다.
정답 코드
let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n, m] = input.shift().split(' ').map(Number);
const graph = input.map(line => line.split(''));
const visited = Array.from({ length: n }, () => new Array(m).fill(0)); // 0: 미방문, 1: 방문 중, 2: 방문 완료
let safeZone = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (visited[i][j] === 0) {
dfs(i, j);
}
}
}
function dfs(x, y) {
const cycle = [];
while (true) {
visited[x][y] = 1;
cycle.push([x, y]);
const [dx, dy] = dir(graph[x][y]);
x += dx;
y += dy;
if (x < 0 || y < 0 || x >= n || y >= m) return;
if(visited[x][y] === 1){
for(let [r,c] of cycle){
if(x === r && y ===c){
safeZone+=1;
break;
}
}
return;
}else if(visited[x][y] === 2){
return;
}
}
// 탐색 완료된 곳을 2로 표시
for (let [r, c] of cycle) {
visited[r][c] = 2;
}
}
function dir(direction) {
switch (direction) {
case 'U': return [-1, 0];
case 'D': return [1, 0];
case 'L': return [0, -1];
case 'R': return [0, 1];
}
}
console.log(safeZone);
정답 코드 2
//방향대로 움직여
//상하좌우
//최소개수 safe zone
//dfs 알고리즘을 활용하자.
//덩어리가 몇개인지 확인
//-그런데, 덩어리가 편입 or 새로운 덩어리
//방문하지 않은 곳이면 dfs 방문
//거기서 dfs 탐색
//해당 좌표 1로
//만약 0이면 하나의 덩어리로
//만약 1이면 그것이 이미 지금 탐색 중인 곳이면, 이제 끝내면서 safe zone +1
//만약 2이면 그냥 편입임. return
let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n,m] = input.shift().split(' ').map(v => +v);
let graph = input.map(el => el.split(''));
const visited = Array.from({length: n}, () => new Array(m).fill(0));
let safeZone = 0;
for(let i=0; i<n; i++){
for(let j=0; j<m; j++){
if(visited[i][j] === 0){
dfs(i,j)
}
}
}
function dfs(x,y){
let dung = [] ;
while(true){
visited[x][y] = 1
dung.push([x,y])
let str = graph[x][y]
let [dx,dy] = dir(str);
let nx = x+dx
let ny = y+dy
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
break;
}
if(visited[nx][ny] === 1){
for(let [r,c] of dung){
if(nx === r && ny === c){
safeZone+=1
break;
}
}
break;
}
if(visited[nx][ny] === 2){
return;
}
x = nx
y = ny
}
for(let [r,c] of dung){
visited[r][c] = 2;
}
}
function dir(str){
switch(str){
case 'U':
return [-1,0]
case 'D':
return [1,0]
case 'L':
return [0,-1]
case 'R':
return [0,1]
default: return [0,0]
}
}
console.log(safeZone)
반응형
'알고리즘 문제 풀기' 카테고리의 다른 글
백준 14500: 테트로미노 - javascript (완탐, dfs) (0) | 2024.10.15 |
---|---|
백준 2589 : 보물섬 - javascript(bfs) (0) | 2024.10.14 |
백준 10159 : 저울 - javascript(dfs) (0) | 2024.10.12 |
백준 20058 : 마법사 상어와 파이어스톰 - javascript(dfs) (0) | 2024.10.10 |
격자 회전 함수 (90도 회전) (3) | 2024.10.10 |