https://www.acmicpc.net/problem/7576
멋쟁이 토마토 토마토
내용은 쉽다
1의 번짐이지
퉁퉁퉁퉁퉁사후르 같은거 기대하고 토마토그려달라햇는데
토마토가 토마토를 먹는 그림이 나옴
무서워
잡설은 그만하고
[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
당연히 bfs 문제인데
다른점이 있다
먼저 생각해야 될 게
1. 1인 곳을 먼저 파악하고 그것들을 토대로, 1이 퍼져나간다. ( 즉 1이 있는곳을 토대로 0을 찾는 bfs )
2. 우리가 지금까지 해왔던 것 처럼, vector와 queue를 하는게 아니라 하나의 queue만 사용한다.
는것이다.
응? 우리가 왜 앞선 문제들에선 전부 벡터를 사용했을까?
사실 벡터의 특성때문에 사용한건 아니고, 그냥 동적으로 배열 정리하고, indexing 하기 쉬워서 사용했던 것
그리고 , 나눠져 있는 연결집합에 대해 구분하려고 사용한 것이고
이것은, 각각 독립된 집합의 문제가 아니라, 전체에 대한 답을 구하는 것이기 때문에 전체적인 배열 하나를 사용한다
음.. 쉽게 설명이 안되긴하네
먼저
1인곳들을 파악하면?
그 위치들을 토대로 왼쪽 오른쪽 위 아래로 퍼지게 해주는데
그 값이 0이고, 방문하지 않은 값이여야 한다!
내용자체는 쉬운데
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
queue<pair<int, int>> q;
int n, m;
bool visited[1000][1000];
int arr[1000][1000];
int dp[1000][1000];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void made_1();
int max1 = 0;
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
cin >> arr[i][j];
if (arr[i][j] == 1)
{
q.push(make_pair(i, j));
dp[i][j] = 0;
}
}
made_1();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (arr[i][j] == 0)
{
cout << -1 << "\n";
return 0;
}
}
cout << max1 << "\n";
}
void made_1()
{
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
visited[x][y] = true;
// cout << "x : " << x << ", y : " << y << "\n";
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m)
{
if (!visited[nx][ny] && arr[nx][ny] == 0)
{
// cout << nx << " " << ny << "\n";
dp[nx][ny] = dp[nx - dx[i]][ny - dy[i]] + 1;
max1 = max(dp[nx][ny], max1);
visited[nx][ny] = true;
arr[nx][ny] = 1;
q.push(make_pair(nx, ny));
}
}
}
}
}
참고로 가로가 m 세로가 n인것을 생각해야 된다. 이거 모르고 좀 헤맸다.
어느정도 인터넷의 도움을 받고 내가 직접 코드를 짯긴 했지만 뭔가 이해가 확실하게 안되는 부분이 있었는데
바로 걸린 날짜이다
나는 저번 미로찾기 문제때와 같이 dp를 사용해서 풀었는데
과연 그 값이 max라고 확정지을 수 있을까?
그렇다
근데 아마 나보다 똑똑한 사람들은 이미 눈치챘을거다
저런상황 안생긴다
왜냐?
if (nx >= 0 && ny >= 0 && nx < n && ny < m)
{
if (!visited[nx][ny] && arr[nx][ny] == 0)
{
// cout << nx << " " << ny << "\n";
dp[nx][ny] = dp[nx - dx[i]][ny - dy[i]] + 1;
max1 = max(dp[nx][ny], max1);
visited[nx][ny] = true;
arr[nx][ny] = 1;
q.push(make_pair(nx, ny));
}
}
여기 조건문에서 보면 q.push가 되는 과정을 보면, 퍼지는 과정이 모두 순서대로 일어난다(fifo인 q의 특성을 통해)
즉 dp가 3인 값들에 대한 자식노드들의 익힘이 퍼지고 난 후 >> dp가 4인값들이 차례대로 발생되는 것이다.
쨋든그러하다