인프런 커뮤니티 질문&답변

안녕하세요 민규님 ㅎㅎ

첫번째 질문으로는 제가 구현한 코드가 너무 비효율적인 것 같습니다. 어떻게하면 이 코드에서 더 좋은 코드로 발전시킬 수 있을까요?

>> 코드리뷰를 드리자면요.

1. 이게 보시면. 4방향을 탐색할 때 return하는 부분이 너무 비효율적입니다.

예를 들어 왼쪽을 탐색하고 해당 for문을 아예 종료를 시켜버립니다.

즉, 이 코드는 4방향 탐색이라고도 할 수 없습니다. 한방향에서 1이라면 dfs돌리고 return 하거든요.

        if(ajm[ny][nx] == 1){
            dfs(ny,nx,ajm);
            return;
        }

그렇다면 결국...

나머지 방향들은 처음 시작 이중 for 문에 의존하여 실행되게 되는 것이죠.

    for(int i = 0; i < n; i++){
        for(int j= 0; j < m; j++){
            if(ajm[i][j] == 1){
                dfs(i, j, ajm);
            }
        }
    }

지금 문제야... 디버깅코드를 찍어보시면.

start
0 : 4
1 : 4
2 : 4
3 : 4
3 : 3
2 : 3

이런식으로 한방향을 기준으로 탐색하다가... -> -> 다시 되는 방향 찾아가지고... (아래로) 이런식으로 됩니다.

그러나 이런 코드는.

이렇게 탐색해야할 때 아래쪽을 전혀 탐색을 못하게 되겠죠? 이런 단점이 있습니다.

참고 : 디버깅 코드.

#include <bits/stdc++.h>
using namespace std;

const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, findCount = 0;

void dfs(int y, int x, int **ajm){
    cout << y << " : " << x << "\n";
    ajm[y][x] = 0;
    int check = 0;
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= n || nx < 0 || nx >= n) {
            check++;
            if(check == 4){
                findCount++;
                return;
            }
            continue;}
        if(ajm[ny][nx] != 1) {
            check++;
            if(check == 4){
                findCount++;
                return;
            }
            continue;
        }
        if(ajm[ny][nx] == 1){
            dfs(ny,nx,ajm);
            return;
        }
    }
}
int main(){
    int num;
    cin >> n >> m;
    int **ajm = new int*[n];
    for(int i = 0; i < n; i++){
        ajm[i] = new int[m];
    }

    for(int i = 0; i < n; i++){
        for(int j= 0; j < m; j++){
            cin >> ajm[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j= 0; j < m; j++){
            if(ajm[i][j] == 1){
                cout << "start\n";
                dfs(i, j, ajm);
            }
        }
    }
    cout << findCount;
    return 0;
}

2. 원본배열은 왠만하면 수정하지 않는게 좋습니다.

void dfs(int y, int x, int **ajm){
    ajm[y][x] = 0;

지금이야 0으로 바꿔도 괜찮다고 생각합니다. 다만 문제가 복잡해지면.. 원본배열 수정했는데 또 꼬이는 경우가 많이 있어서 visited배열을 따로 두는게 더 좋을 것 같습니다.

두번째 질문으로는 제가 구현한 방식을 dfs라고 할 수 있는걸까요? 그냥 감으로 작성한 코드라서 이게 될줄 몰랐습니다.

>>

네 dfs가 맞습니다. 재귀적으로 호출하고 있는 부분도 있고 ajm를 수정하면서 가기 때문에 종료도 잘 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

/*
연결된 육지는 모두 오염
바다로는 갈 수 없다.
오염시킬수 있는 방향은 상 하 좌 우 네방향
최소 몇번을 이동해야 모든 육지를 오염시킬 수 있는가?
1 : 육지 0 : 바다

범위 
1 <= N <= 100
1 <= M <= 100

예제 입력

입력은 맵의 세로길이 N과 가로길이 M이 주어진다. N * M의 맵이 주어진다.
5 5
1 0 1 0 1
1 1 0 0 1
0 0 0 1 1
0 0 0 1 1
0 1 0 0 0

출력
4
*/
#include <bits/stdc++.h>
using namespace std;

const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, findCount = 0;

void dfs(int y, int x, int **ajm){
    ajm[y][x] = 0;
    int check = 0;
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= n || nx < 0 || nx >= n) {
            check++;
            if(check == 4){
                findCount++;
                return;
            }
            continue;}
        if(ajm[ny][nx] != 1) {
            check++;
            if(check == 4){
                findCount++;
                return;
            }
            continue;
        }
        if(ajm[ny][nx] == 1){
            dfs(ny,nx,ajm);
            return;
        }
    }
}
int main(){
    int num;
    cin >> n >> m;
    int **ajm = new int*[n];
    for(int i = 0; i < n; i++){
        ajm[i] = new int[m];
    }

    for(int i = 0; i < n; i++){
        for(int j= 0; j < m; j++){
            cin >> ajm[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j= 0; j < m; j++){
            if(ajm[i][j] == 1){
                dfs(i, j, ajm);
            }
        }
    }
    cout << findCount;
    return 0;
}