개발 블로그

문제 링크 : https://www.acmicpc.net/problem/1759

import java.util.*;

public class BOJ_1759_암호만들기 {

    static boolean[] visited;
    static char[] arr;
    static int L, C;
    static boolean chk(String str){
        int cnt1 = 0; //모음
        int cnt2 = 0; //자음
        for(int i = 0; i<str.length(); i++){
            if(str.charAt(i)=='a' || str.charAt(i)=='e' || str.charAt(i)=='i' || str.charAt(i)=='o' || str.charAt(i)=='u'){
                cnt1++;
            }
            else cnt2++;
            if(cnt1>=1 && cnt2>=2) return true;
        }
        return false;
    }

    static void dfs(int start, String str){
        if(str.length()==L){
            if(chk(str)){
                System.out.println(str);
                return;
            }

        }
        for(int i = start; i<C; i++){
            if(visited[i]==false){
                str = str + arr[i];
                visited[i] = true;
                dfs(i+1, str);
                str = str.substring(0, str.length()-1);
                visited[i] = false;
            }
        }


    }



    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        L = sc.nextInt();
        C = sc.nextInt();
        arr = new char[C];
        visited = new boolean[C];


        for(int i = 0; i<C; i++){
            arr[i] = sc.next().charAt(0);
            visited[i] = false;
        }
        Arrays.sort(arr);
        String initStr = "";

        dfs(0, initStr);

    }
}

문제 링크 : https://www.acmicpc.net/problem/17070

문제

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가로

세로

대각선

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

입력

첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

출력

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.

접근 방법

DFS를 활용한 재귀로 완전탐색을 해 준다.

dr[], dc[]에 가로, 세로, 대각선 방향의 수를 저장하고 for()문에서 가로,세로,대각선을 반복하면서 파이프의 끝 위치를 옮긴다.

이때, 가능한 조합 중, "가로->세로 "와 "세로->가로"는 이동할 수 없는 조합이므로, 이를 제외한다. 

또한 주의할 점은 대각선일 때이다.

아래의 그림처럼 파이프의 끝이 (2,3) -> (3,4)로 이동하는 경우에, (3,4)뿐만 아니라 (2,4)와 (3,3)도 모두 벽이 아니어야 이동할 수 있기 때문에 이 두개 중 벽이 하나라도 있는 경우는 제외한다.

DFS()를 돌다가 파이프의 끝이 (N,N) 도달하면 카운트를 하나 증가한다.

//
//  BF_BOJ17070_파이프옮기기1.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/08/12.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N;
int map[17][17];
int dr[3] = {0,1,1};
int dc[3] = {1,0,1};
int answer= 0;

//범위 체크 and 벽 체크
bool chk(int r, int c)
{
    if (r < 1 || r > N || c < 1 || c > N || map[r][c] == 1) return false;
    else return true;
}

void DFS(int r, int c, int dir){

    if(r==N && c==N){
        answer++;
        return;
    }

    for(int i = 0; i<3; i++){
        //가로->세로 or 세로->가로 안됨
        if((dir==0 && i==1) || (dir==1 && i==0)) continue;

        int nr = r + dr[i];
        int nc = c + dc[i];
        if(chk(nr,nc)==false) continue;     //범위 벗어나거나 벽이면 
        if(i==2 && (map[r+1][c]==1 || map[r][c+1]==1)) continue;    //대각선인데 나머지 칸이 벽이면 
        DFS
    (nr, nc, i);

    }
}

int main()
{

    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> map[i][j];
        }
    }

    DFS(1,2, 0);
    cout << answer;

    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/3040

문제

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.

어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.

백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.

아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)

입력

총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.

출력

일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.

접근 방법

DFS 를 이용해서 9명 중 7명을 뽑았을 때 난쟁이 번호의 합이 100이 되는지 검사한다. 정답을 찾으면 true 를 리턴해서 DFS를 빠져나왔을 때 탐색을 진행하지 않고 종료한다.

좀 더 시간을 줄이기 위해 DFS의 첫번째 파라미터를 이용해서 중복 조합으로 난쟁이들을 뽑았다. 두명을 뽑는다고 했을 때, (1번 난쟁이, 2번 난쟁이)를 뽑는 것과 (2번 난쟁이, 1번 난쟁이) 를 뽑는 것이 같기 때문이다.

import java.util.*;
public class DFS_BOj3040_백설공주와일곱난쟁이 {

	static int[] numArr, visited;
	static ArrayList<Integer> ansList = new ArrayList<Integer>(); 
	
	public static boolean DFS(int start, int toPick, int sum) {
		if(toPick==0 && sum==100) {
			for(int i = 0; i<ansList.size(); i++) {
				System.out.println(ansList.get(i));
			}
			return true;
		}
		
		for(int i = start; i<9; i++) {
			if(visited[i] == 0) {
				visited[i] = 1;
				ansList.add(numArr[i]);
				if(DFS(i, toPick-1, sum + numArr[i])==false) {
					ansList.remove(ansList.size()-1);
					visited[i] = 0;
				}
				else break;
			}
		}
		return false;
	}
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		numArr = new int[9];
		visited = new int[9];
		
		for(int i = 0; i<9; i++) {
			numArr[i] = sc.nextInt();
		}
		
		DFS(0,7,0);	
	}
}

문제 링크 : www.acmicpc.net/problem/2210

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

배열을 char 형으로 설정해서 string의 push_back(), 

//
//  DFS_BOJ2210_숫자판점프.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

char map[5][5];
//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};

vector<string> strVec;
void DFS(int r, int c, int toPick, string str){
        
    if(toPick==0){
        if(find(strVec.begin(), strVec.end(), str) == strVec.end()){
            strVec.push_back(str);
        }
        return;
    }
    
    for(int i = 0; i<4; i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if(nr<0 || nr>=5 || nc<0 || nc>=5) continue;
        
        str.push_back(map[nr][nc]);
        DFS(nr, nc, toPick-1,str);
        str.pop_back();
    }
}

int main(){
    
    for(int i = 0; i<5; i++){
        for(int j = 0; j<5; j++){
            cin >> map[i][j];
        }
    }
    
    for(int i = 0; i<5; i++){
           for(int j = 0; j<5; j++){
               DFS(i,j,6, "");
           }
    }

    cout << strVec.size();
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/14889

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

접근 방법

sumFunc이 DFS이다. 

DFS 돌면서 각각 팀의 능력치를 더한다.

그 능력치의 차를 구해서 최소가 되는 경우를 찾는다.

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int N;
int map[21][21];
int visited[21] = {0};
int num;

vector<int> start;
vector<int> link;

int chk[11] = {0};

vector<int> vec;
vector<int> sumVec;
int ans1 = 0;
int ans2= 0;
int ans = 100000000;


vector<int> sSum;

//DFS 돌면서 팀의 능력치 더함
void sumFunc(int toPick, vector<int> vec){
    
    if(toPick==0){
        
        int sum =  map[sumVec[0]][sumVec[1]] + map[sumVec[1]][sumVec[0]];
        sSum.push_back(sum);
        return;
    }
    
    for(int i = 0; i<vec.size(); i++){
        if(chk[i] ==0){
            chk[i] = 1;
            sumVec.push_back(vec[i]);
            sumFunc(toPick-1, vec);
            sumVec.pop_back();
            chk[i] = 0;
            
        }
    }
    
    
}


void choiceFunc(int toPick, int num){
    
    
    if(toPick==0){
        ans1 = 0; ans2 = 0;
        link.clear();
		
        //스타트와 링크 각각 start, link 벡터에 나눔
        for(int j = 1; j<=N; j++){
            if(visited[j]==0) {
                link.push_back(j);
            }
        }

        //스타트
        sumFunc(2, start);
        for(int i = 0; i<sSum.size(); i++){
            ans1+=sSum[i];
        }
        sSum.clear();
        
        //링크
        sumFunc(2, link);
        for(int i = 0; i<sSum.size(); i++){
            ans2+=sSum[i];
        }
        sSum.clear();


        if(ans1<ans2){		//더 큰게 ans1이 되게 바꿈
            int tmp=ans1;
            ans1=ans2;
            ans2=tmp;
        }
        
        if(ans1-ans2 < ans){ans = ans1-ans2;}	//능력치 차가 최소인 것 구함 
        memset(chk, 0, sizeof(chk));
        
        return;
        
    }
    
    for(int i = 1; i<=N; i++){
        
        if(visited[i]==0 && num<i){
            visited[i] = 1;
            start.push_back(i);
            choiceFunc(toPick-1, i);
            start.pop_back();
            visited[i] = 0;
            
        }
    }
    
}



int main(){
    
    cin >> N;
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            cin >> map[i][j];
        }
    }

    num = (N*(N-1)) / 4;
    
    choiceFunc(N/2, 0);
    
    cout << ans/2 ;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/14501

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 1일2일3일4일5일6일7일TiPi

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

접근 방법

파라미터 start를 바꿔가며 DFS를 돈다. 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int T[15] = {0};
int P[15] = {0};

int ans = 0;

void dfs(int start, int sum){
    
    if(start>N) return;
    
    ans = max(ans, sum);
    
    for(int i = start; i<N; i++){
        dfs(i+T[i], sum+P[i]);		//시작일을 바꿔가며 최대 sum 체크
    }
        

}


int main(){
    
    cin >> N;
    for(int i = 0; i<N; i++){
        cin>> T[i] >> P[i];
    }
    
    dfs(0,0);
    cout << ans << "\n";
    return 0;
}

문제 링크 : www.acmicpc.net/problem/1759

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

접근 방법

DFS를 돌면서 ansVec벡터에 알파벳들을 push하고, toPick을 L부터 0까지 감소시켜나간다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<char> alpha;
vector<char> ansVec;
int visited[15] = {0};

//문제 조건 만족하는지 체크 : 모음 최소 1개 포함 and 암호 최소 길이 3
bool chk(){
    int cntV = 0;   //모음
    int cntC = 0;   //자음
    for(int i = 0; i<ansVec.size(); i++){
        if(ansVec[i]=='a' || ansVec[i]=='e' || ansVec[i]=='i' || ansVec[i]=='o' || ansVec[i]=='u') {cntV++;}
        else cntC++;
    }
    if(cntV>=1 && cntC>=2) return true;
    else return false;

}



void dfs(int toPick, char c){
    
    if(toPick==0){
        if(chk()){
            for(int i = 0; i<ansVec.size(); i++){
                cout << ansVec[i];
            }
            cout << "\n";
        }
        return;
    }
    
    
    for(int i = 0; i<alpha.size(); i++){
        
        if(visited[i]==0 && c<=alpha[i]){	//중복가능하니 등호 포함(c<=alpha[i])
            visited[i] = 1;
            ansVec.push_back(alpha[i]);
            dfs(toPick-1, alpha[i]);
            ansVec.pop_back();
            visited[i] = 0;
            
        }
        
    }
    
}
int main(){
    
    int L,C;
    cin >> L >> C;
    
    for(int i = 0; i<C; i++){
        char c; cin >> c;
        alpha.push_back(c);
    }
    
    sort(alpha.begin(), alpha.end());
    dfs(L, 'a');	//암호 알파벳 중복 가능하니까 초기값 'a'로 설정해도 상관 x
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/2667

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

접근 방법

map[0][0] ~ map[N-1][N-1] 까지 돌면서 방문하지 않은 곳에서 dfs를 호출한다. 호출하기 전에 cnt를 1로 초기화 한 뒤, dfs 함수 안에서 재귀로 dfs가 재호출 될 때마다 연결된 단지로 전진한 것이므로 cnt를 1씩 증가해준다. 처음에 호출한 dfs가 끝나면 cnt를 cntVec안에 push 해서 마지막에 출력할 수 있도록 저장하고, 단지 그룹 1개를 다 탐색한 것이므로 res를 1 증가시킨다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int map[25][25];
int visited[25][25];
vector<int> cntVec;

//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};
int N;
int cnt;

void dfs(int r, int c){

    for(int i = 0; i<4; i++){
        
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if(nr>=N || nr<0 || nc>=N || nc<0) continue;
        
        if(visited[nr][nc]==0 && map[nr][nc]==1){   //방문 안했고 집이 있으면
            visited[nr][nc] = 1;                    //방문했다고 표시하고
            cnt+=1;                                 //집 개수 세기
            dfs(nr,nc);
        }
    }
 
}


int main(){
    
    int res=0;
    
    cin >> N;
    string str;
    
    for(int i = 0; i<N; i++){
        cin >> str;
        for(int j = 0; j<str.length(); j++){            //입력 주의
            visited[i][j] = 0;
            
            if(str[j] == '1'){
                map[i][j] = 1;
            }
            else map[i][j] = 0;
        }
    }
    
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            
            if(map[i][j]==1 && visited[i][j]==0){
                visited[i][j] = 1;
                cnt = 1;                        //처음은 시작점 포함하므로 1로 초기화
                dfs(i,j);
                cntVec.push_back(cnt);
                res++;                          //단지 그룹 1개 탐색 끝남
            }
        }
    }
    
    sort(cntVec.begin(), cntVec.end());
    cout << res << "\n";
    
    for(int i = 0; i<cntVec.size(); i++){
        cout << cntVec[i] << "\n";
    }

    return 0;
}