https://www.acmicpc.net/problem/4963
[DFS,BFS] 백준 2667번 단지 번호 붙이기(C++)
[DFS,BFS] 백준 2667번 단지 번호 붙이기(C++)
https://www.acmicpc.net/problem/2667 [DFS,BFS] 백준 1260번 BFS와 DFS(C++) 이문제, 당연히 BFS와 DFS 문제를 풀고 와야 겠지? 내용 자체는 쉽다그림으로만 딱 봐도 보이잖나?그럼 어떻게 풀까? 앞선 BFS나 DFS문제들
lee-soo.tistory.com
혹은
[DFS,BFS] 백준 1260번 BFS와 DFS(C++)
[DFS,BFS] 백준 1260번 BFS와 DFS(C++)
https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시를 보여주겠다 먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다 대략 이렇게 그려져 있다 그
lee-soo.tistory.com
를 꼭 보고 오길 바란다
특히 단지 번호 붙이기와 매우 유사한 문제
해당 문제는 단지 번호 붙이기에서 n * m으로 바뀌고 대각선도 고려한다는 것도 나온다
그렇다면? 대각선을 고려해주는 조건문과 n*n이 아닌 n*m으로 바꿔주면된다
앞서서 우리가 고려한 것은
이렇게 고려한 것인데
단지 문제에서 뒤쪽은 왜 고려안하는지 얘기를 했었고
그렇다면
이번문제에서 더 바라볼 것은 대각선인데 "왼쪽아래 오른쪽아래 대각선"을 고려해야 한다.
이유는, 말 안해도 알것이다, 그 이후것만 고려하는데 당연히 왼쪽아래 대각선도 이후의 경우니까
그럼 간단하게
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
bool visited[50 * 50 + 1];
vector<int> island[50 * 50 + 1];
int whole = 0;
int arr[50 * 50 + 1];
int n, m;
void bfs(int alpha);
int main()
{
while (1)
{
cin >> m >> n;
if (n == 0 && m == 0)
return 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> arr[i * m + j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
int x = i * m + j;
if (arr[x])
{
if (((x + 1) % m) != 0 && arr[x + 1])
{
island[x].push_back(x + 1);
island[x + 1].push_back(x);
}
if (!(((x + m) > n * m)) && arr[x + m])
{
island[x].push_back(x + m);
island[x + m].push_back(x);
}
if (!((x + m + 1 > n * m) || (x + m + 1) % m == 0) && arr[x + m + 1])
{
island[x].push_back(x + m + 1);
island[x + m + 1].push_back(x);
}
if (!((x + m - 1 > n * m) || ((x + m - 1) % m == m - 1)) && arr[x + m - 1])
{
island[x].push_back(x + m - 1);
island[x + m - 1].push_back(x);
}
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
int temp = i * m + j;
if (!visited[temp] && arr[temp] == 1)
bfs(temp);
}
}
cout << whole << "\n";
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
int k = i * m + j;
island[k].clear(); // 그래프 초기화
visited[k] = false; // 방문 초기화
arr[k] = 0;
}
}
whole = 0;
}
}
void bfs(int alpha)
{
queue<int> p;
p.push(alpha);
visited[alpha] = true;
whole++;
while (!p.empty())
{
int temp = p.front();
p.pop();
for (int k = 0; k < island[temp].size(); k++)
{
if (!visited[island[temp][k]])
{
visited[island[temp][k]] = true;
p.push(island[temp][k]);
}
}
}
}
이것 역시 내가 2차원 배열로 안하고 1차열 배열로 했는데, 2차원 배열로 꼭 해봐라.. 숫자 커지면 머리아프다.
또한 테트로미노 문제를 풀때, 4방향 배열을 미리 선언해놓은 방법으로 푸는것도 좋은 방법일 것 같다.