[0608~0609] 알고리즘

  맨날 뭔가의 기법을 이용한 문제를 풀어보겠다고 설치지만 오늘(06.09)도 그러지 못했다.

 

---

1051. 숫자 정사각형

  브루트 포스 문제. 다른 건 다 괜찮았고 최댓값 구하는 함수가 algorithm 헤더에 있다길래 그거 써봤다. 조만간 이거 구성도 살펴봐야지 싶었음.

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

int main()
{
  std::cin.tie(NULL);

  int n, m, maxSq = 1;

  std::cin >> n >> m;

  //n x m 크기 직사각형 입력받기
  std::vector<std::vector<int>> square(n, std::vector<int> (m, 0));
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      scanf("%1d", &square[i][j]);
    }
  }

  //n x m 크기 직사각형 안에서 만들어질 수 있는 최대크기의 정사각형 한 변
  int max = std::min(n, m);
  //std::cout << max << '\n';

  if (max > 1)
  {
    for (int i = 2; i <= max; i++)
    {
      for (int j = 0; j <= n - i; j++)
      {
        for (int k = 0; k <= m - i; k++)
        {
          if (square[j][k] == square[j][k + i - 1] && square[j][k] == square[j + i - 1][k] && square[j][k] == square[j + i - 1][k + i - 1])
          {
            maxSq = i;
            break;
          }
          //조건에 만족하는 정사각형 단 하나라도 발견하면 바로 다음 반복으로
          if (maxSq == i) break;
        }
      }
    }
  }  
  
  std::cout << (maxSq * maxSq) << '\n';
  return 0;
}

  사각형 속 요소들이 띄어쓰기 없이 들어와서 이걸 입력받으려고 scanf를 사용하였다.

 

 

 

1743. 음식물 피하기

  아마 DFS로 푼 문제... 예전에 과제로 풀었던 모든 경로의 수 찾기랑 비슷하게 푼 것 같다.

  몇 번 틀렸었는데 DFS 함수를 실행하는 조건에 '해당 좌표를 방문했는가?' 를 추가하여서 일단은 맞았다. 구체적으로 뭐가 문제였는지는 자고 일어나서 다시 생각해봐야할 것 같다.

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

int n, m, k, max = 0, num = 0;
int path[101][101];
bool memory[101][101];

void DFS(int x, int y);

int main()
{
  std::cin.tie(NULL);
  std::ios_base::sync_with_stdio(false);

  std::cin >> n >> m >> k;

  //방문 여부 기록 배열 초기화
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      memory[i][j] = false;
    }
  }

  //쓰레기 넣기
  for (int i = 0; i < k; i++)
  {
    int x, y;
    std::cin >> x >> y;
    path[x - 1][y - 1] = 1;
  }

  //탐색
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (path[i][j] == 1 && !memory[i][j]) 
      {
        num = 0;
        DFS(i, j);
        if (num > max) max = num;
      }
    }
  }

  std::cout << max << '\n';

  return 0;
}

void DFS(int x, int y)
{  
  num++;
  memory[x][y] = true;

  if (x != 0 && path[x - 1][y] == 1 && !memory[x - 1][y])
  {
    DFS(x - 1, y);
  }
  if (x != n - 1 && path[x + 1][y] == 1 && !memory[x + 1][y])
  {
    DFS(x + 1, y);
  }
  if (y != 0 && path[x][y - 1] == 1 && !memory[x][y - 1])
  {
    DFS(x, y - 1);
  }
  if (y != m - 1 && path[x][y + 1] == 1 && !memory[x][y + 1])
  {
    DFS(x, y + 1);
  }
}