[백준 BOJ] 1388번 바닥 장식 (C++/cpp)

문제 설명

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

1388번: 바닥 장식

 

접근 방법 - 깊이 우선 탐색(DFS) 이용한 연산 문제

백준의 1388번 문제는 DFS 및 BFS를 이용하여 연산을 수행해야 하는 문제이다.

해당 문제는, 입력값에 대하여 필요한 총 나무판자의 개수를 세어 출력해야 하는 문제이다.

필자는 BFS보다는 DFS에 더욱 적합한 문제라 판단하여 DFS를 이용하여 해결해보았다.

여기서 BFS는 너비 우선 탐색이며 DFS는 깊이 우선 탐색인데, 이에 대한 개념이 아예 없다면 우선은 검색을 해본 뒤에 해결을 시도해보는 것이 더 좋을 것 같다.

DFS 개념에 대한 이해가 다소 부족하거나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 바닥 장식에 대한 정보를 입력받을 배열(arr)을 전역 변수로 선언해둔다. 

그리고 탐색을 수행할 시 방문 여부를 저장할 배열(visit)도 int형 전역 변수로 선언해둔다.

 

2) 방바닥의 크기(n, m)와 그에 따른 바닥 장식의 정보(arr)를 차례로 입력받는다.

 

3) 필요한 총 나무판자의 개수를 저장할 변수 cnt를 0으로 초기화하여 선언한다.

 

4) 반복문을 통해, arr의 값들을 하나씩 탐색하며 아래의 연산을 취한다.

(이때 visit 배열에 있어, 배열값이 0이라면 방문하지 않은 경우이며 1이라면 방문을 완료한 경우임을 뜻한다.)

- 만일, 현재 arr의 탐색값이 -(가로)이며 아직 방문하지 않은 값이라면 아래의 연산을 취한다.

- 우선 나무판자가 하나는 필요한 상태가 되었으니, cnt에 1을 더한다.
- 가로 나무판자에 대한 연산을 수행하는 dfs1() 함수를 실행한다.
현재 위치를 방문했음을 나타내기 위해, 현재 위치에 대한 visit 배열값을 1로 저장한다.
옆 방향으로 다음 arr의 배열값이 -(가로)라면 해당 위치에 대하여 dfs1() 함수를 실행한다. (재귀)

- 만일, 현재 arr의 탐색값이 |(세로)이며 아직 방문하지 않은 값이라면 아래의 연산을 취한다.

- 이 경우에도 나무판자가 하나는 필요한 상태가 되었으니, cnt에 1을 더한다.
- 세로 나무판자에 대한 연산을 수행하는 dfs2() 함수를 실행한다.
현재 위치를 방문했음을 나타내기 위해, 현재 위치에 대한 visit 배열값을 1로 저장한다.
아래 방향으로 다음 arr의 배열값이 |(세로)라면 해당 위치에 대하여 dfs2() 함수를 실행한다. (재귀)

 

5) 모든 연산이 완료되었다면, 최종적으로 저장된 cnt의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 1388번 코드
int visit[51][51];
string arr[51];

void dfs1(int i, int j){ // -인 경우
    visit[i][j]=1;
    if(arr[i][j+1]=='-'){
        dfs1(i, j+1);
    }
}

void dfs2(int i, int j){ // |인 경우
    visit[i][j]=1;
    if(arr[i+1][j]=='|'){
        dfs2(i+1, j);
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]=='-' && visit[i][j]==0){
                cnt++;
                dfs1(i, j);
            }
            else if(arr[i][j]=='|'&& visit[i][j]==0){
                cnt++;
                dfs2(i, j);
            }
        }
    }

    cout<<cnt<<endl;
}

 

제출 결과

(2022.07.07 백준 1388번 문제 제출 결과)