모각코 Part 3

지금까지 코딩 테스트를 본 결과, 그래프 문제가 조금 약한 것 같아 DFS, BFS, 완전 탐색, 백트래킹 등과 같은 문제 유형을 풀어보았습니다.

 

1. 영역 나누기 (백준 2583, 실버 1)

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

int m, n, k;
int area[100][100];
int check[100][100];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
vector<int> res;
int cnt = 1;

void dfs(int y, int x){
  check[y][x] = 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)
      continue;
    if(check[ny][nx] == 0 && area[ny][nx] == 0){
    // 영역이면 넓이 추가
      cnt++;
      dfs(ny, nx);
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> m >> n >> k;
  int x, y, xx, yy;
  int ans = 0;
  for(int i = 0; i < k; i++){
    cin >> x >> y >> xx >> yy;
    for(int j = x; j < xx; j++){
      for(int l = y; l < yy; l++){
        area[l][j] = 1;
      }
    }
  }

  for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
      if(area[i][j] == 0 && check[i][j] == 0){
        dfs(i, j);
        // 재귀가 끝나면 한 덩어리 탐색이 끝났다는 뜻
        ans++;
        // 구한 영역 넓이 저장
        res.push_back(cnt);
        // 영역 초기화
        cnt = 1;
      }
    }
  }
  cout << ans << "\n";
  sort(res.begin(), res.end());
  for(int a : res)
    cout << a << " ";
  cout << "\n";
  return 0;
}

2. 쿼드트리 (백준 1992, 실버 1)

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

int n;
int arr[64][64];
string ans = "";

void recur(int y, int x, int len){
  // 재귀 탈출 조건
  if(len == 1){
    ans += to_string(arr[y][x]);
    return;
  }
  
  bool all_zero = true, all_one = true;
  for(int i = y; i < y+len; i++){
    for(int j = x; j < x+len; j++){
      // 1이 1개라도 있으면 모두 0인 조건 false
      if(arr[i][j] == 1){
        all_zero = false;
      }
      // 0이 1개라도 있으면 모두 1인 조건 false
      else{
        all_one = false;
      }
    }
  }
  // 모두 0이면 0추가
  if(all_zero && arr[y][x] == 0){
    ans += "0";
    return;
  }
  // 모두 1이면 1추가
  else if(all_one && arr[y][x] == 1){
    ans += "1";
    return;
  }
  // 그 외는 괄호 추가하고 각 사분면 나눠서 다시 재귀
  else{
    ans += "(";
    // 1
    recur(y, x, len/2);
    // 2
    recur(y, x+len/2, len/2);
    // 3
    recur(y+len/2, x, len/2);
    // 4
    recur(y+len/2, x+len/2, len/2);
    ans += ")";
  }
} 

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  string s;

  for(int i = 0; i < n; i++){
    cin >> s;
    for(int j = 0; j < s.size(); j++){
      arr[i][j] = s[j] -'0';
    }
  }
  // 0, 0부터 시작
  recur(0, 0, n);
  cout << ans << "\n";
  return 0;
}

3. 효율적인 해킹 (백준 1325, 실버 1)

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

int n, m;
// 각 컴퓨터당 해킹할 수 있는 컴퓨터 수 저장 배열
int arr[10001];
// 인접 리스트 사용
vector<int>vec[10001];
int check[10001];

int dfs(int here){
  check[here] = 1;
  int link = 1;
  for(int a : vec[here]){
    if(check[a] == 0)
      link += dfs(a);
  }
  return link;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  int a, b;
  // b를 해킹하면 a도 해킹할 수 있으니 b에 a를 추가
  for(int i = 0; i < m; i++){
    cin >> a >> b;
    vec[b].push_back(a);
  }

  int maximum = INT_MIN;
  for(int i = 1; i <= n; i++){
    // check배열 초기화
    memset(check, 0, sizeof(check));
    // i를 해킹했을 때 해킹할 수 있는 컴퓨터의 수 저장
    arr[i] = dfs(i);
    maximum = max(maximum, arr[i]);
  }
  for(int i = 1; i <= n; i++){
    if(arr[i] == maximum)
      cout << i << " ";
  }
  cout << "\n";

  return 0;
}

4. 트리 (백준 1068, 골드 5)

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

int n, r;
// 인접 리스트
vector<int> vec[51];

// 각 노드의 자녀 노드가 없을 때까지 재귀
int dfs(int here){
  int child = 0, ret = 0;
  for(int there : vec[here]){
    // 삭제된 노드 부분은 스킵
    if(there == r)
      continue;
    child++;
    ret += dfs(there);
  }
  if(child == 0)
    return 1;
  return ret;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  int node, root;
  for(int i = 0; i < n; i++){
    cin >> node;
    if(node == -1)
      root = i;
    else
      vec[node].push_back(i);
  }
  cin >> r;

  // 지울 노드가 루트일 때
  if(r == root){
    cout << "0\n";
    return 0;
  }
  cout << dfs(root) << "\n";
  return 0;
}

5. 치킨 배달 (백준 15686, 골드 5)

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

int n, m;
int area[50][50];
int answer = INT_MAX;
vector<pair<int, int>> chicken, house;
// 치킨 집 m개 선점
vector<vector<int>> choice;

// 조합 치킨 집 n개 중 m개를 선택하는 과정
void combi(int start, vector<int> v){
  if(v.size() == m){
    choice.push_back(v);
    return;
  }
  for(int i = start + 1; i < chicken.size(); i++){
    v.push_back(i);
    combi(i, v);
    v.pop_back();
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  int data;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin >> data;
      // 치킨집인 구역 저장
      if(data == 2)
        chicken.push_back({i, j});
      // 집인 구역 저장
      else if(data == 1)
        house.push_back({i, j});
    } 
  }
  vector<int> v;
  combi(-1, v);

  for(auto c : choice){
    int sum = 0;
    for(auto h : house){
      int chicken_dist = INT_MAX;
      // 뽑은 m개의 치킨집과 각 집을 비교해 각 집의 최소치킨거리를 구하고 도시의 치킨거리에 더함
      for(auto a : c){
        int dist = abs(h.first - chicken[a].first) + abs(h.second - chicken[a].second);
        chicken_dist = min(chicken_dist, dist);
      }
      sum += chicken_dist;
    }
    // 치킨 최단 거리 갱신
    answer = min(answer, sum);
  }
  cout << answer << "\n";
  return 0;
}

6. 보물섬 (백준 2589, 골드 5)

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

int n, m;
char area[50][50];
int check[50][50];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int answer = INT_MIN;

void bfs(int y, int x){
  // bfs 실행될 때마다 check 배열 초기화
  memset(check, 0, sizeof(check));
  check[y][x] = 1;
  queue<pair<int, int>> q;
  q.push({y, x});
  while(!q.empty()){
    int y = q.front().first;
    int 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 || ny >= n || nx < 0 || nx >= m)
        continue;
      if(check[ny][nx] == 0 && area[ny][nx] == 'L'){
        // bfs 최단 경로 찾을 때와 마찬가지로 1씩 추가하며 길 개수 더하기
        check[ny][nx] = check[y][x] + 1;
        q.push({ny, nx});
        // 가장 먼 육지 갱신
        answer = max(answer, check[ny][nx]);
      }
    }
  }
}

int main(){
  ios::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 >> area[i][j];
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
    // 육지인 지역을 찾을 때마다 가장 멀리 있는 육지 지역을 찾는 bfs 실행
      if(area[i][j] == 'L')
        bfs(i, j);
    }
  }
  cout << answer - 1<< "\n";
  return 0;
}

7. 인구 이동 (백준 16234, 골드 5)

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

int n, l, r;
int area[50][50];
int check[50][50];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int sum = 0;
vector<pair<int, int>> vec;

void dfs(int y, int x){
  check[y][x] = 1;
  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)
      continue;
    // 이동할 수 있는 조건일 경우
    if(check[ny][nx] == 0 && abs(area[y][x] - area[ny][nx]) >= l && abs(area[y][x] - area[ny][nx]) <= r){
      // 연합된 지역의 인구 총 합 계산
      sum += area[ny][nx];
      // 연합된 지역 저장
      vec.push_back({ny, nx});
      dfs(ny, nx);
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> l >> r;
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin >> area[i][j];
    }
  }
  bool flag = true;
  // 이동 횟수
  int res = 0;

  while(flag){
    flag = false;
    memset(check, 0, sizeof(check));
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        if(check[i][j] == 0){
          vec.clear();
          sum = area[i][j];
          vec.push_back({i, j});
          dfs(i, j);
          if(vec.size() > 1){
            flag = true;
            // 연합된 지역끼리의 인구 갱신
            for(auto a : vec){
              area[a.first][a.second] = sum / vec.size();
            }
          }
        }
      }
    }
    // 더이상 이동할 수 없을 때
    if(!flag)
      break;
    // 더 이동할 수 있다면 반복
    else 
      res++;
  }
  
  cout << res << "\n";

  return 0;
}

8. 연구소 (백준 14502, 골드 4)

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

int n, m;
int area[9][9], check[9][9];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
// 벽을 세울 위치 저장할 배열
vector<pair<int, int>> vec;

void dfs(int y, int x){
  check[y][x] = 1;
  for(int i = 0; i < 4; i++){
    int ny = dy[i] + y;
    int nx = dx[i] + x;
    if(ny < 0 || ny >= n || nx < 0 || nx >= m)
      continue;
    if(check[ny][nx] == 0 && area[ny][nx] == 0)
      dfs(ny, nx);
  }

}

int solve(){
  memset(check, 0, sizeof(check));
  // 바이러스가 다 퍼지는 곳은 2로 지정
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(area[i][j] == 2)
        dfs(i, j);
    }
  }
  // 그 외 나머지 부분은 dfs로 안전 영역 개수 확인
  int ret = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(area[i][j] == 0 && check[i][j] == 0)
        ret++;
    }
  }
  return ret;
}

int main(){
  ios::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 >> area[i][j];
  }

  // 벽이 있는 곳 저장
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(area[i][j] == 0)
        vec.push_back({i, j});
    }
  }

  // 빈 곳 중 벽 세울 3곳 선정 nC3
  int answer = 0;
  for(int i = 0; i < vec.size(); i++){
    for(int j = 0; j < i; j++){
      for(int k = 0; k < j; k++){
        area[vec[i].first][vec[i].second] = area[vec[j].first][vec[j].second] = area[vec[k].first][vec[k].second] = 1;
        // 바이러스가 퍼지는 것을 계산하고, 안전 영역 수가 가장 많은 것 갱신
        answer = max(answer, solve());
        // 벽으로 지정했던 곳을 다시 풀어줘야 함
        area[vec[i].first][vec[i].second] = area[vec[j].first][vec[j].second] = area[vec[k].first][vec[k].second] = 0;
      }
    }
  }
  cout << answer << "\n";
  return 0;
}