백준 1388: 바닥 장식 - javascript(이중 for문, dfs)

문제 출처 

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

1388번: 바닥 장식

문제

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.

기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1 복사

4 4
----
----
----
----

예제 출력 1 복사

4

예제 입력 2 복사

6 9
-||--||--
--||--||-
|--||--||
||--||--|
-||--||--
--||--||-

예제 출력 2 복사

31

예제 입력 3 복사

7 8
--------
|------|
||----||
|||--|||
||----||
|------|
--------

예제 출력 3 복사

13

예제 입력 4 복사

10 10
||-||-|||-
||--||||||
-|-|||||||
-|-||-||-|
||--|-||||
||||||-||-
|-||||||||
||||||||||
||---|--||
-||-||||||

예제 출력 4 복사

41

예제 입력 5 복사

6 6
-||--|
||||||
|||-|-
-||||-
||||-|
||-||-

예제 출력 5 복사

19

 

문제 풀이 힌트 

이중 for문을 사용할 수도 있고, dfs를 활용할수도 있다. 

먼저 이중 for문 방식의 코드부터 ! 말해보자 ~

 

(dfs 방식으로 푼건 요기로 이동 !)
https://fordang.tistory.com/114

백준 1388: 바닥 장식 - javascript(이중 for문, dfs)

문제 풀이 코드 

01. 이중 for문

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); //각 줄을 기준으로 배열로 만든다. 
const [N,M] = input.shift().split(' ').map(v => +v); //첫번째 줄을 input 배열에서 빼서 split으로 배열로 나누고, 숫자 타입으로 바꿔준다. 
const room = input.map(v => v.split('')); //input 각 줄로 나눠진 배열을 하나의 요소로 나눠지도록 배열로 나눠준다. 
function solution(N,M,room){
    let count = 0; //판자 몇개 필요한지? 
    for(let i=0; i<N; i++){ //가로 idx
        let flag = false; //flag는 이전에 '-'이거였는지 나타낸다. 맨 가로줄의 첫줄은 이전의 요소가 없으니 flag === false 이다.   
        for(let j=0; j<M; j++){ //세로 idx 
            if(!flag && room[i][j] === '-'){//이전의 요소가 '-'가 아니고, 현재의 요소가 '-'일 때 
                count++; 
                flag = true; //내가'-'였다는 사실을 체크할게 
            }else if(room[i][j] === '|'){//만약 '|'이라면,
                flag = false; //내가 '-'가 아니였다는 사실을 체크할게 
            }
        }
    }
    for(let i=0; i<M; i++){//세로 idx
        let flag = false; //flag는 이전에 '|'이거였는지 나타낸다. 맨 세로줄의 첫줄은 이전의 요소가 없으니 flag === false 이다.   
        for(let j=0; j<N; j++){//가로 idx
            if(!flag && room[j][i] === '|'){//이전의 요소가 '|'가 아니면서, 현재의 요소가 '|'일때, 
                count++; 
                flag = true; //내가'|'였다는 사실을 체크할게 
            }else if(room[j][i] === '-'){ //만약 현재의 요소가 '-'라면, 
                flag = false; //내가'|'가 아니였다는 사실을 체크할게 
            }
        }
    }
    return count; 
}
const answer = solution(N,M,room)
console.log(answer);

Only 풀이 코드 

01. 이중 for문 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [N,M] = input.shift().split(' ').map(v => +v); 
const room = input.map(v => v.split('')); 

function solution(N,M,room){
    let count = 0; 
    for(let i=0; i<N; i++){
        let flag = false; 
        for(let j=0; j<M; j++){
            if(!flag && room[i][j] === '-'){
                count++; 
                flag = true; 
            } else if(room[i][j] === '|'){
                flag = false; 
            }
        }
    }
    for(let i=0; i<M; i++){
        let flag = false; 
        for(let j=0; j<N; j++){
            if(!flag && room[j][i] === '|'){
                count++; 
                flag = true; 
            } else if(room[j][i] === '-'){
                flag = false; 
            }
        }
    }
    return count; 
}

const answer = solution(N,M,room)
console.log(answer);