inflearn logo
강의

講義

知識共有

10週間完成 C++ コーディングテスト | アルゴリズムコーディングテスト

2-P

코드 리뷰 요청드립니다!

6

smilechild10054627

投稿した質問数 1

0

저는 행렬이 더 편해서 이렇게 했는데, 선생님 코드는 연결리스트로 하셨더라구요.

괜찮을까 싶어서 질문 남깁니다.

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

int N, M, temp, Map[10][10], tempMap[10][10], visited[10][10], mx;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

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

void cleanMap(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            Map[i][j] = tempMap[i][j];
        }
    }
}

int getSafeArea(){
    int cnt = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(Map[i][j] == 0) cnt++;
        }
    }
    return cnt;
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> temp;
            tempMap[i][j] = temp;
        }
    }
    int sz = N*M;
    // 최대 64칸에서 순서 상관없이 3개를 뽑는다 -> 64C3
    for(int i = 0; i < sz; i++){
        if(tempMap[i/M][i%M] != 0) continue;
        for(int j = i + 1; j < sz; j++){
            if(tempMap[j/M][j%M] != 0) continue;
            for(int k = j + 1; k < sz; k++){
                if(tempMap[k/M][k%M] != 0) continue;
                cleanMap();
                Map[i/M][i%M] = 1;
                Map[j/M][j%M] = 1;
                Map[k/M][k%M] = 1;
                for(int l = 0; l < N; l++){
                    for(int m = 0; m < M; m++){
                        if(Map[l][m] == 2) {
                            visited[l][m] = 1;
                            dfs(l, m);
                        }
                    }
                }
                int sa = getSafeArea();
                if(mx < sa) mx = sa;
            }
        }
    }
    cout << mx << '\n';
}

c++ 코딩-테스트

回答 1

0

communityai8509

안녕하세요, 인프런 AI 인턴입니다.

김성은님께서 작성하신 것처럼 2차원 배열(행렬)로 맵을 구현해도 괜찮습니다. 연결 리스트는 인접한 칸을 표현하는 또 다른 방법일 뿐이며, 이 문제처럼 크기가 작고 격자 형태인 경우에는 오히려 2차원 배열이 더 직관적입니다.

코드의 전체적인 흐름도 적절합니다.

  • 벽을 놓을 빈칸 3개를 조합으로 선택
  • tempMapMap에 복사
  • 선택한 위치에 벽 설치
  • 바이러스 위치에서 DFS 수행
  • 안전 영역의 크기 계산
  • 가장 큰 값을 갱신

다만 다음 부분은 참고하시면 좋습니다.

  1. visited 배열은 현재 사용되지 않으므로 제거해도 됩니다. dfs()에서 방문한 칸을 3으로 변경하고 있기 때문에 Map 자체가 방문 배열 역할을 하고 있습니다.
  2. tempMap에서 바이러스 위치를 순회할 때, Map을 오염시키기 전에 모든 바이러스 위치를 기준으로 DFS를 시작하는 현재 방식은 정상적으로 동작합니다.
  3. dfs()의 재귀 깊이는 최대 격자 크기만큼 발생할 수 있으므로, 문제의 제한이 커진다면 BFS 또는 명시적인 스택을 고려할 수 있습니다.
  4. cleanMap()을 매번 호출하는 방식도 현재 제한에서는 충분합니다. 다만 조합마다 배열을 복사하는 대신, 벽을 설치하고 DFS한 뒤 해당 위치를 다시 0으로 되돌리는 백트래킹 방식으로도 작성할 수 있습니다.

행렬을 사용한 DFS 구현과 방문 처리 방식에 대한 유사한 코드 리뷰는 아래 게시글을 참고해 주세요.

해당 답변에서도 2차원 배열을 이용한 DFS 구현에 대해 다루고 있으며, 재귀 호출을 통한 탐색과 방문한 칸을 표시하는 방법, 4방향 탐색 시 주의할 점을 설명하고 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

코딩살구클럽 계정 문의

0

32

2

SK하이닉스 대비 강의수강

0

80

3

코딩살구클럽 등록부탁드립니다.

0

47

2

7-F 재귀로 풀시 런타임애러

0

49

1

1-N 문제 질문입니다. (+ 채점오류)

0

52

2

코딩살구클럽 가입 확인 부탁드립니다.

0

70

2

직장인 코테 합격 공부방법 문의

0

77

2

코딩살구클럽 가입 방법

0

70

2

6-H 체점 관련 질문

0

47

1

채점서버 연결 관련 질문입니다

0

79

2

삼성 s직군

0

71

1

삼성 코테 없어짐

0

162

1

코딩살구클럽 가입부탁드립니다

0

69

2

코딩살구클럽 가입 요청 확인부탁드립니다

0

58

2

5-S 테스트 케이스 질문

0

60

2

코살 문제풀이 환경

0

75

2

2 - T 오큰수 문제가 있는 것 같습니다.

0

61

1

추천 추가문제들

0

55

2

프로그래머스 코테 환경 관련해서 질문드립니다.

0

76

2

해당 문제에 대한 채점이 코딩살구클럽에서 올바르게 처리되지 않습니다.

0

61

2

균형 이진 트리 설명 시 높이 숫자

0

58

2

4-H 질문드립니다.

0

51

2

1-K 질문드립니다.

0

63

2

대기업 인적성 시험 질문

0

62

2