코테 노트/백준

백준 13565 침투 C++

화요밍 2021. 8. 30. 21:25
728x90
반응형

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

 

13565번: 침투

첫째 줄에는 격자의 크기를 나타내는  M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않

www.acmicpc.net

 

최종 코드

 

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

백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.

github.com

//
//  main.cpp
//  BJ13565.cpp
//
//  Created by Hwayeon on 2021/08/30.
//

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

int M, N;
int fiber[1000][1000] = {0, };
int visit[1000][1000] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
bool check = false;

void bfs(int s){
    queue<pair<int,int>> q;
    q.push({s, 0});
    visit[0][s] = 1;
    while(!q.empty() && !check){
        int now_x = q.front().first;
        int now_y = q.front().second;
        q.pop();
        for(int i=0; i<4; 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(fiber[ny][nx] == 0){
                visit[ny][nx] = 1;
                q.push({nx, ny});
                if(ny == M-1){
                    check = true;
                    break;
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> M >> N;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            scanf("%1d", &fiber[i][j]);
        }
    }
    for(int i=0; i<N; i++){
        if(check) break;
        if(fiber[0][i] == 0) bfs(i);
    }
    if(check) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

 

 

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

백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.

github.com

//
//  main.cpp
//  BJ13565.cpp
//
//  Created by Hwayeon on 2021/08/30.
//

#include <iostream>
#include <string.h>
using namespace std;

int M, N;
int fiber[1000][1000] = {0, };
int visit[1000][1000] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
bool check = false;

void dfs(int x, int y){
    if(y == M-1){
        check = true;
        return;
    }
    if(check) return;
    for(int i=0; i<4; 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(fiber[ny][nx]) continue;
        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++){
            scanf("%1d", &fiber[i][j]);
        }
    }
    for(int i=0; i<N; i++){
        if(check) break;
        memset(visit, 0, sizeof(visit));
        if(!fiber[0][i]) {
            visit[0][i] = 1;
            dfs(i, 0);
        }
    }
    if(check) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

풀이 과정

풀이 시간 16분

 Outer line의 전류가 흐르는 칸에 전류를 발생시켰을 때, Inner line까지 전류가 흐를 수 있는지를 판단하는 문제이다.

즉, 그래프 완전 탐색 알고리즘인 BFS나 DFS 알고리즘을 활용하여 탐색을 진행하고, Inner line까지 탐색이 가능한지를 확인하면 된다.

 

 전형적인 BFS, DFS 알고리즘을 활용하였으니 시간복잡도는 O(N(V+E))= O(N(N*M + 4*N*M)) = O(N^3)이다.

이때, 입력이 N=1000, M=1000인 경우가 가장 최악의 경우이고, 인접한 4방향으로 탐색이 이뤄지니 E = 4*N*M = 4,000,000이다.

하지만, visit 배열을 이전에 방문한 경우, 방문을 진행하지 않기 때문에 4,000,000,000번의 연산 횟수보다 훨씬 적은 연산을 할 것으로 예상된다.

DFS 알고리즘을 활용해 문제를 푼 결과
BFS를 활용하여 문제를 푼 결과

 두 가지 방법을 적용하여 각각의 시간이 얼마나 걸렸는지 확인해보면 DFS 알고리즘을 사용한 경우가 2배 정도 더 시간이 소요되는 걸 확인할 수 있다. 그 이유는 DFS를 구현할 때 재귀 함수를 이용하면 코드가 간결해지는 장점이 있지만, 재귀 호출을 통해 수시로 변수 값이 변화하며 메모리 사용량이 증가한다.  Context switching이 빈번하게 발생하기 때문이다. 따라서 BFS보다 DFS가 속도가 더 느리다.

 

1. BFS

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

int M, N;
int fiber[1000][1000] = {0, };
int visit[1000][1000] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
bool check = false;

void bfs(int s){
    queue<pair<int,int>> q;
    //q에 현재 시작 노드의 위치 값을 push, 현재 시작 노드 방문 처리
    q.push({s, 0});
    visit[0][s] = 1;
    //더이상 탐색할 노드가 없거나, 이미 inner side까지 전류가 흐른 경우 탐색 종료
    while(!q.empty() && !check){
        int now_x = q.front().first;
        int now_y = q.front().second;
        q.pop();
        
        //인접한 4 방향 탐색
        for(int i=0; i<4; 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(fiber[ny][nx] == 0){
                visit[ny][nx] = 1;
                q.push({nx, ny});
                //노드의 ny가 inner side인 경우, 침투에 성공했으므로 check를 true로 바꾸고 더이상 탐색을 진행하지 않는다
                if(ny == M-1){
                    check = true;
                    break;
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> M >> N;
    for(int i=0; i<M; i++){
    	//입력이 띄어쓰기 없이 N자리 정수형으로 들어오기 때문에, 하나씩 정수를 받아온다
        for(int j=0; j<N; j++){
            scanf("%1d", &fiber[i][j]);
        }
    }
    
    //outer side = row = 0의 모든 col에 대하여 bfs 탐색을 시작
    for(int i=0; i<N; i++){
    	//이미 이전 bfs 탐색에서 전류가 inner side에 침투 가능하다고 확인된 경우, bfs 탐색을 멈춘다
        if(check) break;
        //(x, y) = (i, 0)을 시작 노드로 bfs를 탐색
        if(fiber[0][i] == 0) bfs(i);
    }
    if(check) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}
//시간복잡도 = O(N(V+E))= O(N(N*M + 4*N*M)) = O(N^3), 공간복잡도 = O(N^2)

 

2. DFS

#include <iostream>
#include <string.h>
using namespace std;

int M, N;
int fiber[1000][1000] = {0, };
int visit[1000][1000] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
bool check = false;

void dfs(int x, int y){
	//inner side에 전류가 흐른 경우, check를 true로 바꾸고 dfs 탐색을 종료한다
    if(y == M-1){
        check = true;
        return;
    }
    //이미 inner side에 전류가 흐른 경우, 탐색을 더이상 하지 않는다
    if(check) return;
    
    //인접한 4 방향 탐색
    for(int i=0; i<4; 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(fiber[ny][nx]) continue;
        
        //전류가 흐르는 칸인 경우, 방문 처리 후 dfs 탐색을 이어간다
        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++){
           	//입력이 띄어쓰기 없이 N자리 정수형으로 들어오기 때문에, 하나씩 정수를 받아온다
            scanf("%1d", &fiber[i][j]);
        }
    }
    
    //outer side = row = 0의 모든 col에 대하여 dfs 탐색을 시작
    for(int i=0; i<N; i++){
        //이미 이전 dfs 탐색에서 전류가 inner side에 침투 가능하다고 확인된 경우, dfs 탐색을 멈춘다
        if(check) break;
        
        //visit 배열 초기화
        memset(visit, 0, sizeof(visit));
        
        //전류가 흐르는 칸이면 방문 처리 후 dfs 탐색 시작
        if(!fiber[0][i]) {
            visit[0][i] = 1;
            dfs(i, 0);
        }
    }
    if(check) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}
//시간복잡도 = O(N(V+E))= O(N(N*M + 4*N*M)) = O(N^3), 공간복잡도 = O(N^2)

오답 노트

 입력이 M개의 줄에 N자리의 정수가 하나씩 들어오게 된다. 즉 배열에 넣어줄 때, 한 자리씩 끊어서 넣어줘야한다.

	for(int i=0; i<M; i++){
        int row;
        cin >> row;
        for(int j=N-1; j>=0; j—){
            fiber[i][j] = row%10;
            row/=10;
        }
    }

처음 문제를 풀 때, 위와 같이 10을 나눈 나머지 값을 N-1~0번째 인덱스에 차례대로 넣어줬는데, 2%에서 실패가 떴다.

테스트케이스 몇 개를 넣어보고 배열값을 출력했을 때는 잘 들어간 거를 확인했는데, 왜인지 모르겠다... (혹시 아시는 분이 있다면 댓글을 남겨주시길🙏🏻🙏🏻)

 

 결국, scanf를 사용하여 한 자리씩 받아오도록 바꿔주니 문제를 해결할 수 있었다.

728x90
반응형

'코테 노트 > 백준' 카테고리의 다른 글

백준 14716 현수막 C++  (0) 2021.08.31
백준 1303 전쟁 - 전투 C++  (0) 2021.08.30
백준 1058 친구 C++  (0) 2021.08.26
백준 3184 양 C++  (0) 2021.08.24
백준 2210 숫자판 점프 Python3  (0) 2021.08.22

'코테 노트/백준'의 다른글

  • 현재글백준 13565 침투 C++

관련글

댓글

티스토리툴바