1926 그림 / BFS (장고)

문제 링크

무난한 그래프 탐색 문제이고 BFS, DFS로 풀 수 있는데 나는 BFS로 풀어보았다.

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

int n,m;
const int MAX = 501;
int map[MAX][MAX]={0,}; // 입력값 저장
int visited[MAX][MAX]={0,};
int dy[] = {-1, 0, 1, 0}; // 시계방향
int dx[] = {0, 1, 0, -1};  // 시계방향
queue<pair<int,int>> q; // BFS 사용 큐
vector<int> v; // 그림 개수 저장 벡터
int s = 1; // 그림 넓이

void bfs(int y, int x){
	visited[y][x] = true;
    q.push(make_pair(y,x));
    
    while(!q.empty()){
    	y = q.front().first;
        x = q.front().second;
        q.pop();
        
        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] == 1 && visited[ny][nx]==0){
            	visited[ny][nx]=true;
                s++; // 그림 넓이 카운트해주기
                q.push(make_pair(ny,nx));
            }
        }
    }
}

// 벡터 오름차순 정렬을 위해~
bool compare(int i, int j){
	return i > j;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	cin >> n >> m;
    for(int i=0; i<n; i++){
    	for(int j=0; j<m; j++){
        	cin >> map[i][j];
        }
    }
    
    int cnt = 0; // connected component 개수
    for(int i=0; i<n; i++){
    	for(int j=0; j<m; j++){
        	if(map[i][j]==1 && visited[i][j]==0){
            bfs(i,j);
            v.push_back(s);
            cnt++;
            s = 1; // 초기화 해주기~
            }
        }
    }
    sort(v.begin(), v.end(), compare); //벡터 오름차순 정렬
    cout << cnt << endl;
    if(cnt == 0){
    	cout << 0 << endl;
    }
    else{
    	cout << v[0] << endl;
    }
}

---

2667 단지 번호 붙이기 / DFS (장고)

문제 링크

무난한 그래프 탐색 문제이고 BFS, DFS로 풀 수 있는데 나는 DFS로 풀어보았다.
지도의 정보를 담은 2차원 배열 map , 방문했는지 판단하기 위한 visited 2차원 배열, 그리고 답을 출력하기 위한 resVec 벡터를 선언했다.

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

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

int dy[4] = {-1, 0, 1, 0}; // 시계방향
int dx[4] = {0, 1, 0, -1}; // 시계방향
int n, cnt;

void dfs(int y, int x){
	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 > =n) continue;
        if(visited[ny][nx] == 0 && map[ny][nx] == 1){
			// 아직 방문하지 않은 집이 있다면
            visited[ny][nx] == 1; // 방문 표시
            cnt += 1;
            dfs(ny,nx); // 재귀
        }
    }
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	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); // 시작
                resVec.push_back(cnt);
                res++; // 단지 그룹 1개 탐색 끝남
            }
        }
    }
    
    sort(resVec.begin(), resVec.end()); //오름차순 정렬
    cout << res << "\n"; // 단지 개수
    
    for(int i = 0; i < resVec.size(); i++){
    	cout << resVec[i] << "\n";
    }
    return 0;
}

---

2468 안전영역

문제링크
최소, 최대, 없거나, 있거나 반례를 체크해줘야 한다.

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

int a[101][101], visited[101][101], n, ret = 1; // 비가 안올 때도 생각해서 ret을 1로 초기화를 해줘야 한다.
int dy[4]={-1,0,1,0}, dx[4]={0,1,0,-1};

void dfs(int y, int x, int d)
{
    visited[y][x]=1;
    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 >= n) continue;
        if(!visited[ny][nx] && a[ny][nx] > d) 
            dfs(ny, nx, d);
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> a[i][j];
        }
    }
    // depth 검토
    for(int d=1; d<101; d++)
    {
        // 테스트케이스마다 초기화해줘야 한다
        fill(&visited[0][0], &visited[0][0]+ 101*101, 0);
        int cnt = 0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(a[i][j] > d && !visited[i][j])
                {
                    dfs(i, j, d);
                    cnt++;
                }
            }
        }
        ret = max(ret, cnt);
    }
    cout << ret << '\n';
    return 0;
}

---

2583 영역 구하기

문제링크
문제에서 주어진 사각형을 기반으로 영역을 만들고 나머지 영역의 사이즈를 구해 벡터에 담아서 오름차순으로 정렬해서 출력하면 된다.

#include<bits/stdc++.h>
using namespace std;
#define y1 aaaa
int a[104][104], m,n,k,x1,x2, y1,y2, visited[104][104];
const int dy[4]={-1,0,1,0};
const int dx[4]={0,1,0,-1};
vector<int> ret;
int dfs(int y, int x) // int 반환 dfs 를 만드는 것이 핵심이다
{
    visited[y][x]=1;
    int ret = 1;
    for(int i=0; i<4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny<0 || ny>= m || nx<0 || nx>=n || visited[ny][nx]==1) continue;
        if(a[ny][nx]==1) continue;
        ret += dfs(ny, nx);
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> m >> n >> k;
    for(int i=0; i<k; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        for(int x = x1; x < x2; x++)
        {
            for(int y = y1; y < y2; y++)
            {
                a[y][x] = 1;
            }
        }
    }
    // 나머지 영역으로부터 connected component 얻어오기
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(a[i][j] != 1 && visited[i][j]==0)
            {
                ret.push_back(dfs(i,j));    
            }
        }
    }
    sort(ret.begin(), ret.end());
    cout << ret.size() << '\n';
    for(int a : ret) cout << a << " ";
    return 0;
}

---

2828 사과 담기 게임

문제링크

#include <bits/stdc++.h>
using namespace std;
int n,m,j,l,r,temp,ret;
int main()
{
    cin >> n >> m >> j;
    l=1;
    for(int i=0; i<j; i++)
    {
        r=l+m-1; // 새로 정의
        cin >> temp;
        if(temp>=l && temp<=r) continue; // 사과가 바구니에 걸치면 continue
        else
        {
        	// l 수정
            if(temp<l)
            {
                ret+= (l-temp);
                l=temp;
            }
            else
            {
                l+=(temp-r);
                ret+=(temp-r);
            }
        }
    }
    cout << ret << '\n';
    return 0;
}

---

10709 기상캐스터

문제링크
문자를 결국 int형 배열로 만드는 문제이다

int a = 0, cnt = 1;
cout << a = cnt++ << endl; // a 는 1 이다. cnt 도 1이다
cout << cnt << endl; // cnt 가 여기서 2가 된다

int a = 0, cnt = 1;
cout << a = ++cnt << endl; // a 는 2 이다. cnt 도 2이다

위의 예시를 헷갈리지 않도록!!

#include<bits/stdc++.h>
using namespace std;
int n,m,a[104][104]; // H,W,C정보
string s;
int main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++)
    {
        cin >> s;
        for(int j=0; j<m; j++)
        {
            if(s[j]=='.') a[i][j] = -1;
            else a[i][j] = 0;
        }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(a[i][j]==0){
                int cnt = 1;
                while(a[i][j+1] == -1)
                {
                    a[i][j+1]=cnt++;
                    j++;
                }
            }
        }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++) cout << a[i][j] << " ";
        cout << '\n';
    }
    return 0;
}

---