백준 21736: 헌내기는 친구가 필요해 - javascript(dfs)

문제 출처 

https://www.acmicpc.net/problem/21736

21736번: 헌내기는 친구가 필요해

 

문제

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 

도연이가 다니는 대학의 캠퍼스는 �×�$N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (�$x$, �$y$)에 있다면 이동할 수 있는 곳은 (�+1$x+1$, �$y$), (�$x$, �+1$y+1$), (�−1$x-1$, �$y$), (�$x$, �−1$y-1$)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

입력

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 �$N$ (1≤�≤600$ 1 \leq N \leq 600$), �$M$ (1≤�≤600$ 1 \leq M \leq 600$)이 주어진다.

둘째 줄부터 �$N$개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

예제 입력 1 복사

3 5
OOOPO
OIOOX
OOOXP

예제 출력 1 복사

1

예제 입력 2 복사

3 3
IOX
OXP
XPP

예제 출력 2 복사

TT

 

회고 

이제 이런 dfs는 아주 쉽게 느껴지고, 15분 컷 정도 한다. 

이걸 기억하자. 

오늘이 3일차다. 정말 빠르게 습득하고 있고, 할 수 있다. 

내가 또 새롭게 무언가를 알게됐다고 한참 남았다고 생각하지 말자. 

지금 한끗 차이다. 

대신 내가 푼거 완전 암기 및 구조 분석 및 자세한 문법 및 의아한 부분 및 에러가 나는 문법이 있는지 체킹하면서 쌓아가면 된다. 

문제 풀이 힌트 

dfs를 활용해서 풀면 된다. 

이번엔 쉽다. 도연이 I를 찾고 거기서부터 DFS 탐색을 통해 'P'의 개수를 찾으면 된다. 

문제 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [N,M] = input.shift().split(' ').map(v => +v); 
let graph = Array.from({length: N}).map(() => []); //2차원 배열 생성
for(let i=0; i<N; i++){
    graph[i] = input[i].split(''); //생성한 그래프에 값 채우기 
}
//사방면 이동 왼, 오, 위,아래 
const dx = [-1,1,0,0]; 
const dy = [0,0,1,-1]; 

//방문 2차원 배열 생성 
const visited = Array.from({length: N}).map(() => new Array(M).fill(false)); 

//만날 수 있는 P의 개수 
let answer = 0; 

//DFS를 통해서 만날 수 있는 P 개수 세자. 
function dfs(y,x){
    visited[y][x] = true; //방문 체크 
    if(graph[y][x] === 'P') answer++; //만약 방문한 좌표에 P가 있다면 answer++;  
    for(let i=0; i<4; i++){// 사방면 이동 
        let nx = x + dx[i]; 
        let ny = y + dy[i]; 
        if(nx < 0 || ny < 0 || nx >=M || ny >= N) continue; //그래프 벗어나면 아웃
        if(!visited[ny][nx] && graph[ny][nx] !== 'X'){ //방문한적 없는 좌표 && 벽이 아닌 곳
            dfs(ny, nx); 
        }
    }
}

//도연이 위치 찾는것. 
for(let i=0; i<N; i++){
    for(let j=0; j<M; j++){
        if(graph[i][j] === 'I'){
            dfs(i,j); 
            break; //위치 찾았으면 반복문 끝내자.  
        }
    }
}
console.log(answer === 0 ? 'TT' : answer);

Only 문제 풀이 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [N,M] = input.shift().split(' ').map(v => +v); 
let graph = Array.from({length: N}).map(() => []); 
for(let i=0; i<N; i++){
    graph[i] = input[i].split(''); 
}
const dx = [-1,1,0,0]; 
const dy = [0,0,1,-1]; 

const visited = Array.from({length: N}).map(() => new Array(M).fill(false)); 

let answer = 0; 

function dfs(y,x){
    visited[y][x] = true; 
    if(graph[y][x] === 'P') answer++; 
    for(let i=0; i<4; i++){
        let nx = x + dx[i]; 
        let ny = y + dy[i]; 
        if(nx < 0 || ny < 0 || nx >=M || ny >= N) continue; 
        if(!visited[ny][nx] && graph[ny][nx] !== 'X'){
            dfs(ny, nx); 
        }
    }
}

for(let i=0; i<N; i++){
    for(let j=0; j<M; j++){
        if(graph[i][j] === 'I'){
            dfs(i,j); 
            break; 
        }
    }
}
console.log(answer === 0 ? 'TT' : answer);

 

알고가는 ppoint 

01. map이랑 forEach를 완전 능수능란하게 활용할 줄 알아야 한다.