백준 14716 현수막 C++

 

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

14716번: 현수막

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ14726_bfs.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ14726
//
//  Created by Hwayeon on 2021/08/31.
//

#include <iostream>
#include <queue>
using namespace std;

int M, N;
int sign[250][250] = {0, };
int visit[250][250] = {0, };
int letters = 0;

int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

void bfs(int x, int y){
    queue<pair<int, int>> q;
    q.push({x, y});
    visit[y][x] = 1;
    while(!q.empty()){
        int now_x = q.front().first;
        int now_y = q.front().second;
        q.pop();
        for(int i=0; i<8; i++){
            int nx = now_x + dx[i];
            int ny = now_y + dy[i];
            if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
            if(visit[ny][nx] == 1) continue;
            if(sign[ny][nx] == 1){
                visit[ny][nx] = 1;
                q.push({nx, ny});
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> M >> N;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            cin >> sign[i][j];
        }
    }
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            if(sign[i][j] == 1 && visit[i][j] == 0){
                bfs(j, i);
                letters ++;
            }
        }
    }
    cout << letters << endl;
    return 0;
}

 

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ14726_dfs.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ14726
//
//  Created by Hwayeon on 2021/08/31.
//

#include <iostream>
#include <queue>
using namespace std;

int M, N;
int sign[250][250] = {0, };
int visit[250][250] = {0, };
int letters = 0;

int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

void dfs(int x, int y){
    for(int i=0; i<8; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
        if(visit[ny][nx]) continue;
        if(sign[ny][nx] == 1){
            visit[ny][nx] = 1;
            dfs(nx, ny);
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> M >> N;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            cin >> sign[i][j];
        }
    }
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            if(sign[i][j] == 1 && visit[i][j] == 0){
                visit[i][j] = 1;
                dfs(j, i);
                letters ++;
            }
        }
    }
    cout << letters << endl;
    return 0;
}

---

풀이 과정

 현수막의 글자가 있는 모든 칸을 방문하는 완전 탐색 문제이다.

 

1. BFS

풀이 시간 10분

#include <iostream>
#include <queue>
using namespace std;

int M, N;

//현수막 
int sign[250][250] = {0, };
int visit[250][250] = {0, };

//글자 수
int letters = 0;

int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

void bfs(int x, int y){
    queue<pair<int, int>> q;
    
    //처음 시작 노드 위치를 큐에 삽입 후 방문처리
    q.push({x, y});
    visit[y][x] = 1;
    
    while(!q.empty()){
        int now_x = q.front().first;
        int now_y = q.front().second;
        q.pop();
        
        //상,하,좌,우,대각선으로 인접한 칸 탐색
        for(int i=0; i<8; i++){
            int nx = now_x + dx[i];
            int ny = now_y + dy[i];
            
            //현수막 범위를 벗어난 경우, 무시한다
            if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
            
            //이전에 방문한 위치인 경우, 무시한다
            if(visit[ny][nx] == 1) continue;
            
            //현수막에 글자가 있는 경우, 방문처리 후 다음 탐색을 위해 해당 위치를 q에 삽입한다
            if(sign[ny][nx] == 1){
                visit[ny][nx] = 1;
                q.push({nx, ny});
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> M >> N;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            cin >> sign[i][j];
        }
    }
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
        	//글자가 있는 칸이면서 이전에 방문하지 않은 칸인 경우, 해당 칸을 기준으로 bfs 탐색 시작
            if(sign[i][j] == 1 && visit[i][j] == 0){
                bfs(j, i);
                //(x, y) = (j, i) 글자를 시작으로 상,하,좌,우,대각선으로 인접한 모든 글자를 탐색했으므로, 글자수를 카운팅
                letters ++;
            }
        }
    }
    cout << letters << endl;
    return 0;
}
//시간복잡도 = O(n^2), 공간복잡도 = O(n^2)

 

 

2. DFS

풀이 시간 2분

#include <iostream>
#include <queue>
using namespace std;

int M, N;
//현수막
int sign[250][250] = {0, };
int visit[250][250] = {0, };
//글자 수
int letters = 0;

int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

void dfs(int x, int y){
	//상,하,좌,우,대각선에 인접한 위치 탐색
    for(int i=0; i<8; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        //현수막 범위를 벗어난 경우, 무시한다
        if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
        
        //이전에 방문한 위치인 경우, 무시한다
        if(visit[ny][nx]) continue;
        
        //글자인 칸이라면, 방문 처리 후 dfs 탐색을 이어간다
        if(sign[ny][nx] == 1){
            visit[ny][nx] = 1;
            dfs(nx, ny);
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> M >> N;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            cin >> sign[i][j];
        }
    }
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
        	//글자인 칸이면서, 이전에 방문하지 않은 칸인 경우, 해당 칸을 방문 처리 후 시작으로 dfs 탐색을 시작한다
            if(sign[i][j] == 1 && visit[i][j] == 0){
                visit[i][j] = 1;
                dfs(j, i);
                //(x, y) = (j, i)을 기준으로 상,하,좌,우,대각선에 쓰여있는 모든 글자를 탐색했으므로, 글자수 카운팅
                letters ++;
            }
        }
    }
    cout << letters << endl;
    return 0;
}
//시간복잡도 = O(n^2), 공간복잡도 = O(n^2)