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

안녕하세요 효민님 ㅎㅎ

저는 처음부터 그렇게 생각하지 못해서 각 칸마다 4방향을 모두 탐색하는 알고리즘( for(int k=0; k<4; k++) )으로 작성하였습니다. 예제코드는 통과하였지만 제출 하면 틀렸다고 뜸니다..
>>

잘 했는데요 ㅎㅎ 전체적으로 n, m을 헷갈리신 것 같습니다.

	//모든 칸의 벽의 유무를  확인하면서 하나씩 허물어보기  
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){

이부분이랑... 또 다른 부분이 있는데 고쳐봤습니다.

#include <bits/stdc++.h>
using namespace std;   
const int dy[] = {0, -1, 0, 1}; 
const int dx[] = {-1, 0, 1, 0}; 
int visited[51][51], a[51][51], cnt, compSize[2504], n, m, mx, big;
 
int dfs(int y, int x, int cnt){
    if(visited[y][x]) return 0; 
    visited[y][x] = cnt; 
    int ret = 1; 
    for(int i = 0; i < 4; i++){
        if(!(a[y][x] & (1 << i))){
            int ny = y + dy[i]; 
            int nx = x + dx[i]; 
            ret += dfs(ny, nx, cnt); 
        } 
    } 
    return ret; 
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j]; 
        }
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(!visited[i][j]){
                cnt++; 
                compSize[cnt] = dfs(i, j, cnt);  
                mx = max(mx, compSize[cnt]);
            } 
        }
    }
	//모든 칸의 벽의 유무를  확인하면서 하나씩 허물어보기  
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			//네개의 방향에 있는 벽 확인 
			for(int k=0; k<4; k++){
					int a= i+dy[k];
					int b= j+dx[k];

					if(b<0 || a<0 || b>=n || a>=m) continue;
					if( visited[i][j] == visited[a][b]) continue; // 벽 사이의 색칠 값이 다르다면  
					int neww=compSize[visited[i][j]]+compSize[visited[a][b]];
					big=max(big, neww);
					
				}
			
			}	
		}
	
	cout << cnt << "\n";
	cout << mx << "\n";
	cout << big << "\n";
	
	return 0;
} 

2. 또한 compSize[2504] 사이즈를 50이 아닌 2500으로 설정하셨는지도 궁금합니다. compSize의 최댓값은 맵의 크기인 n*m=50이 아닌가요?

    

>> n * m = 2500입니다. 문제 범위를 보시면...

(1 ≤ M, N ≤ 50) / 이렇게 되어있습니다.

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

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

감사합니다.

강사 큰돌 올림.