PS#10 그래프탐색 X, Y 확인 잘하자!

구현이나 아이디어 자체는 어렵지 않았지만 요즘 2차원 벡터의 행렬 크기를 던져줄 때, 계속 행과 열을 헷갈려 잘못쓰는 실수가 잦다.

행의 갯수(Y)를 M으로, 열의 갯수(X)를 N으로 받아왔는데, 이제는 X와 Y로 직관적으로 받도록 수정해야겠다.

그래프 생성

int main()
{
  int Y, X;
  cin >> Y >> X;
  vector<vector<int>> graph(Y, vector<int>(X, 0));

  for (int i = 0; i < Y; i++)
    for (int j = 0; j < X; j++)
      cin >> graph[i][j]; 
 
 	return 0;
 }

---

dfs 탐색

dfs(graph, visited, j, i, X, Y);

---

dfs

vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};

void dfs(vector<vector<int>> &g, vector<vector<bool>> &visited, int x, int y, int mx, int my)
{
  visited[y][x] = true;

  for (int i = 0; i < 4; i++)
  {
    int nx = x + dx[i];
    int ny = y + dy[i];

    if (nx < 0 || ny < 0 || nx >= mx || ny >= my)
      continue;

	//범위처리는 여집합으로 깔끔하게 처리하자.

    if (!v[ny][nx] && g[ny][nx] > 0)
      dfs(g, v, nx, ny, mx, my);
  }
}

이제는 실수! 멈춰!

---

빙산(G4)

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

// 빙산이 두 덩어리 이상으로 나뉘는 최초의 시간(년).
/*
dfs 돌 때, 이전 dfs에서 해당 빙하가 녹아버려 0이 되었다면, 해당 노드를 배제하고 계산해야함.
해당 노드는 2차원 visited 노드로 관리.

dfs에선 빙하 녹이기만 수행
*/

vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};

void dfs(vector<vector<int>> &g, vector<vector<bool>> &v, int x, int y, int mx, int my)
{
  // 해당 노드 방문처리
  v[y][x] = true;

  for (int i = 0; i < 4; i++)
  {
    int nx = x + dx[i];
    int ny = y + dy[i];

    if (nx < 0 || ny < 0 || nx >= mx || ny >= my)
      continue;

    if (!v[ny][nx] && g[ny][nx] > 0)
      dfs(g, v, nx, ny, mx, my);
  }
}

int main()
{
  int Y, X;
  cin >> Y >> X;
  vector<vector<int>> graph(Y, vector<int>(X, 0));
  vector<vector<bool>> visited(Y, vector<bool>(X, false));

  for (int i = 0; i < Y; i++)
    for (int j = 0; j < X; j++)
      cin >> graph[i][j];

  int answer = 0;

  while (true)
  {
    // 조건 초기화
    int piece = 0;
    visited = vector<vector<bool>>(Y, vector<bool>(X, false));

    // 빙하 세기. 처음부터 두 조각일 수 있음.
    for (int i = 0; i < Y; i++)
      for (int j = 0; j < X; j++)
        if (graph[i][j] > 0 && !visited[i][j])
        {
          piece++;
          dfs(graph, visited, j, i, X, Y);
        }

    // 분기처리
    if (piece >= 2)
    {
      cout << answer << endl;

      return 0;
    }

    if (piece == 0)
    {
      cout << 0 << endl;

      return 0;
    }

    // 빙하 녹은양 체크
    vector<vector<int>> melted_amount(Y, vector<int>(X, 0));
    for (int i = 0; i < Y; i++)
      for (int j = 0; j < X; j++)
        if (graph[i][j] > 0)
          for (int k = 0; k < 4; k++)
          {
            int nx = j + dx[k];
            int ny = i + dy[k];

            if (nx < 0 || ny < 0 || nx >= X || ny >= Y)
              continue;

            if (graph[ny][nx] == 0)
              melted_amount[i][j]++;
          }

    // 녹은 빙하 계산
    for (int i = 0; i < Y; i++)
      for (int j = 0; j < X; j++)
        graph[i][j] = max(0, graph[i][j] - melted_amount[i][j]);

    answer++;
  }

  cout << answer << endl;

  return 0;
}