1. 2667 - DFS / 2D
https://www.acmicpc.net/problem/2667
이전에 풀었던 섬 문제와 비슷해보인다.
다른점은 대각선은 취급하지 않는다는 것,
그리고 섬마다 땅 면적을 출력해야한다는 것이다.
그림2처럼 굳이 숫자로 표시해둘 필요는 없을 것 같다.
초등학생들이 참 똑똑하다
한번 풀어본다.
시도
#include <iostream>
using namespace std;
int N;
void DFS(int, int);
bool map[25][25];
int dx[4] = {0,-1,0,1}; //위왼아오
int dy[4] = {1,0,-1,0};
int count = 0;
int sum[26] = {0, }; //0 인덱스는 무시
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
//입력
string s;
for(int i=0;i<N;i++)
{
cin >> s;
for(int j=0;j<N;j++)
{
map[i][j] = s[j] -'0';
}
}
//DFS
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(map[i][j] == 1)
{
count++;
//cout << "map==1 yx : [" << j << "]" << "[" << i << "]" << "\n";
DFS(i,j);
}
}
}
//출력
cout << count;
for(int i=1;i<count+1;i++)
{
cout << "\n" << sum[i];
}
return 0;
}
void DFS(int x, int y)
{
if(map[x][y] == 0)
{
return;
}
else
{
sum[count]++;
map[x][y] = 0;
}
for(int i=0;i<4;i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if(cx < 0 || N < cx || cy < 0 || N < cy)
{
continue;
}
else
{
DFS(cx, cy);
}
}
}반례들도 맞고 답도 나오는데 틀렸다고 한다.
왜?
각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
위의 조건이 있었다.
해당 출력부만 손봐주면 되겠다.
시도 2
출력하기 전 정렬을 해야했고,
버블정렬을 사용하려고 했지만,
1, 3, 2의 순서로 나오게 된다.
확인해보니 if문 내부로 들어가지 않는다
왜?
for(int i=1;i<count+1;i++)
{
for(int j=1;j<count+1-i;j++)
{
if(sum[j] > sum[j+1])
{
int tmp = sum[j+1];
sum[j+1] = sum[j];
sum[j] = tmp;
}
}
}이렇게 바꿔주니 정상적으로 나오는데,
틀렸다고 뜬다.
왜?
해결
#include <iostream>
using namespace std;
int N;
void DFS(int, int);
bool map[26][26];
int dx[4] = {0,-1,0,1}; //위왼아오
int dy[4] = {1,0,-1,0};
int count = 0;
int sum[320] = {0, }; //0 인덱스는 무시
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
//입력
string s;
for(int i=0;i<N;i++)
{
cin >> s;
for(int j=0;j<N;j++)
{
map[i][j] = s[j] -'0';
}
}
//DFS
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(map[i][j] == 1)
{
//cout << "map==1 yx : [" << j << "]" << "[" << i << "]" << "\n";
DFS(i,j);
count++;
}
}
}
//버블정렬
for(int i=0;i<count;i++)
{
for(int j=0;j<count-i-1;j++)
{
if(sum[j] > sum[j+1])
{
int tmp = sum[j+1];
sum[j+1] = sum[j];
sum[j] = tmp;
}
}
}
cout << count;
for(int i=0;i<count;i++)
{
cout << "\n" << sum[i];
}
return 0;
}
void DFS(int x, int y)
{
if(map[x][y] == 0)
{
return;
}
else
{
sum[count]++;
map[x][y] = 0;
}
for(int i=0;i<4;i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if(cx < 0 || N < cx || cy < 0 || N < cy)
{
continue;
}
else
{
DFS(cx, cy);
}
}
}풀이
조건에 맞는 인덱스를 찾았다면
DFS에 넣는다.
count의 값은 초기값이 0이기 때문에,
DFS에선 해당 인덱스로부터 이어진 곳을 다 0으로 반환하고,
반환한만큼 sum[count]에 더하게 된다.
그리곤 count++;
그러면 다음 단지는 sum[1]에 저장이 되는 것이다.
이런식으로 작성을 하였고,
버블정렬에 맞게 작성하였다.
버블정렬의 첫 for문은 무조건 정렬할 배열의 인덱스개수인데,
2번째 for문은 여태까지 정렬을 진행한 수를 빼주고(i)
-1도 빼주어야만 한다.
이게 인덱스가 1부터 시작하면 2번째 for문의 범위가 곤란해진다.
(첫번째 for문을 0부터 시작하게 바꾸면 되긴할텐데)
마지막으로 sum배열의 크기이다.
sum은 단지마다 합을 저장하는 것으로,
단지의 개수가 배열의 크기가 되어야하는데,
125로 정했었는데, 아니었다.
N값이 25가 들어올 수 있다면, 25*25/2를 해서
최대 313개의 단지가 생길 수 있기 때문이다.
따라서 적절히 수정해서 오류를 피했다.
한 문제에 신경써야할 곳이 3개정도 있었다.
1. 2차원배열방식의 입력
2. 최대 단지 개수
3. 정렬
정렬같은 경우에 cpp에서 algorithm관련 라이브러리를 사용하던데,
코테에서 어떻게 나올지 모르기도 하고,
가장 간단한 버블정렬을 사용해보았다.
2. 1012 - DFS / 2D
https://www.acmicpc.net/problem/1012
이전 문제로 치면, 단지수만 구하면 되는 하위호환 문제이다.
평소같으면 하나만 쭉 비교하는 DFS로 풀겠지만,
이번에는 BFS로 풀어보려고 한다.
https://corona-world.tistory.com/70
시도
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dx[4] = {0, -1, 0, 1}; // 위왼아오
int dy[4] = {1, 0, -1, 0};
int map[50][50];
int M, N, K;
int X, Y;
int worm = 0;
queue<pair<int, int>> q;
void BFS(int x, int y);
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int t = 0; t < T; t++)
{
cout << "initialize" << "\n";
// 초기화
cin >> M >> N >> K;
memset(map, 0, sizeof(map));
worm = 0;
// 배추 심기
for (int k = 0; k < K; k++)
{
cin >> X >> Y;
map[Y][X] = 1;
}
// BFS
for(int i=0;i<N; i++)
{
for(int j=0;j<M;j++)
{
if(map[j][i] == 1)
{
cout << "baechu : " << "x :" << i << " y :" << j << "\n";
BFS(i, j);
worm++;
}
}
}
cout << worm << "\n";
}
return 0;
}
// 해당 값부터 진행
void BFS(int x, int y)
{
q.push(make_pair(x, y));
// 해당 좌표에 대한 BFS진행
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
//cout << "baechu : " << "x :" << x << " y :" << y << "\n";
q.pop();
map[y][x] = 0;
for (int i = 0; i < 4; i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if (cx < 0 || cx > X || cy < 0 || cy > Y)
{
if (map[cy][cx] == 1)
{
q.push(make_pair(cx, cy));
}
}
}
}
}
BFS를 통한 0으로 바꾸기가 진행되지 않은 듯 보인다.
왜?
확인해보니 if문 내부로 들어가지 않았다.
시도 2
위처럼 수정하고,
디버그용 출력코드를 작성해보니,
빨간 숫자만 0으로 바뀌었다.
즉, 맨 오른쪽 배추밭은 0으로 바뀌지 않았다.
왜 x가 7까지만??
아... M과 N을 또 헷갈려서 썼구나..
해결
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dx[4] = {0, -1, 0, 1}; // 위왼아오
int dy[4] = {1, 0, -1, 0};
int map[50][50];
int M, N, K;
int X, Y;
int worm = 0;
void BFS(int x, int y);
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int t = 0; t < T; t++)
{
// 초기화
cin >> M >> N >> K; // M가로 N세로
memset(map, 0, sizeof(map));
worm = 0;
// 배추 심기
for (int k = 0; k < K; k++)
{
cin >> X >> Y;
map[Y][X] = 1;
}
// BFS
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
if (map[j][i] == 1)
{
// cout << "baechu : " << "x :" << i << " y :" << j << "\n";
BFS(i, j);
worm++;
}
}
}
cout << worm << "\n";
}
return 0;
}
// 해당 값부터 진행
void BFS(int x, int y)
{
queue<pair<int, int>> q;
q.push(make_pair(x, y));
// 해당 좌표에 대한 BFS진행
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
map[y][x] = 0;
// 4방향에 대해 갈 수 있는 노드를 체크
for (int i = 0; i < 4; i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if (cx < 0 || cx >= M || cy < 0 || cy >= N)
{
continue;
}
if (map[cy][cx] == 1)
{
q.push(make_pair(cx, cy));
}
}
}
}
가장 떨리는 순간인데..
기다리는 중이 지속된다..
해결
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dx[4] = {0, -1, 0, 1}; // 위왼아오
int dy[4] = {1, 0, -1, 0};
int map[50][50];
int M, N, K;
int X, Y;
int worm = 0;
void BFS(int x, int y);
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int t = 0; t < T; t++)
{
// 초기화
cin >> M >> N >> K; // M가로 N세로
memset(map, 0, sizeof(map));
worm = 0;
// 배추 심기
for (int k = 0; k < K; k++)
{
cin >> X >> Y;
map[Y][X] = 1;
}
// BFS
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
if (map[j][i] == 1)
{
// cout << "baechu : " << "x :" << i << " y :" << j << "\n";
BFS(i, j);
worm++;
}
}
}
cout << worm << "\n";
}
return 0;
}
// 해당 값부터 진행
void BFS(int x, int y)
{
queue<pair<int, int>> q;
q.push(make_pair(x, y));
map[y][x] = 0;
// 해당 좌표에 대한 BFS진행
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
// 4방향에 대해 갈 수 있는 노드를 체크
for (int i = 0; i < 4; i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if (cx < 0 || cx >= M || cy < 0 || cy >= N)
{
continue;
}
if (map[cy][cx] == 1)
{
map[cy][cx] = 0;
q.push(make_pair(cx, cy));
}
}
}
}이 문제도 배울게 있던 문제였다.
BFS의 방문 체크 시점에 관한 오류였다.
// 해당 좌표에 대한 BFS진행
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
map[y][x] = 0;
기존의 코드는 위처럼
큐에서 뽑고나서 방문했다고 체크를 했다.
https://www.acmicpc.net/board/view/65303
큐에 넣기 전에 방문표시를 해야하는 이유현재 BFS를 다른 BFS와 동시에 처리하는 경우,
현재 BFS에서 해당 노드를 넣었지만 아직 방문표시를 하지 않아, 다른 BFS에서 참고할 수 있다고 한다.
그렇게 참고하면 똑같은 노드에서 갈 수 있는 노드도 또 똑같을 것이므로,
같은 행위를 계속해서 반복하게 되어 무한루프도 될 수 있다는 의미이다.일단 이해는 했는데
그런 경우가 언제일지 상상은 안된다.
동시에 BFS가 수행되도록 프로그램이 내부적으로 진행되나?
결론은 어짜피 방문표시는
논리상 뽑고 표시하든, 넣을때 표시하든 둘이 기능은 같지만,
동시적으로 처리하는 문제인 경우에는 넣을때 표시하는것이 더 효율적이다.
따라서 큐에 넣을때 방문표시를 해라!
해당 문제를 BFS로 푸는것은 DFS로 푸는 것과 별반 다르지 않았다.
오히려 같았다고 봐야한다.
for문을 돌며 1인 부분이면 DFS나 BFS를 넣는다.
그리고 해당 좌표로부터 DFS, BFS를 진행하며 값을 수정하거나 수집한다.
끝
하나 다른점은 BFS를 사용하고 좌표값을 받으려면,
queue<pair<int, int>>과 같이 queue를 개조해야하고,
값을 넣을 때에도 q.push(make_pair(cx, cy)); 이렇게 넣어야만 한다.
그리고 이번 문제도 X,Y축이 계속 헷갈렸다.
기능을 구현한건 15분인데..
좌표라는 약점을 찾았다..
3. 2468 - DFS / 2D
https://www.acmicpc.net/problem/2468
문제가 많이 기니 링크 참고.
일단 문제가 마음에 든다.
내가 모자란 2차원 배열을 활용하는 DFS문제이고,
비가 많이오는 현재 상황이랑 잘 맞는 듯 하다.
물에 잠기는 영역이 아닌, 물에 잠기지 않는 영역에 대한
DFS의 대표적인 문제인 섬 문제와 비슷해보인다.
제한높이를 for문을 돌며 각 높이마다 DFS를 해야할 것으로 보인다.
해결
#include <iostream>
#include <cstring>
using namespace std;
int N;
int map[100][100];
bool visited[100][100];
void DFS(int, int);
int height = 0;
int maxIsland = 1; // 0이면 height를 다 할 필요가 없음 // 0의 높이로 잠기게 한 값 //최대섬
int thisIsland; // 현재 개수
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
memset(map, 0, sizeof(map));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> map[j][i];
}
}
// 최대 높이가 100이기때문에 100을 포함할 필요가 없다.
for (int t = 1; t < 100; t++)
{
memset(visited, false, sizeof(visited));
thisIsland = 0;
height = t; // t 높이 까지의 지역을 잠기게 함
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
// 해당 높이 이상이고, 방문하지 않았다면 해당 점을 기준으로 DFS진행
if (map[j][i] > t && !visited[j][i])
{
visited[j][i] = 1;
DFS(i, j);
thisIsland++;
}
}
}
// thisIsland가 0이면 다음 물높이에서도 모두 잠길것이므로 바로 break;
if(thisIsland == 0)
{
break;
}
if(maxIsland < thisIsland)
{
maxIsland = thisIsland;
}
}
cout << maxIsland;
return 0;
}
void DFS(int x, int y)
{
for (int i = 0; i < 4; i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if (cx < 0 || cy < 0 || cx >= N || cy >= N)
{
continue;
}
// 해당 점을 기준으로 갈 수 있는 곳이라면,
else
{
// 갈 수 있고 방문하지 않은 곳이라면,
if (!visited[cy][cx] && map[cy][cx] > height)
{
visited[cy][cx] = 1;
DFS(cx, cy);
}
}
}
}
완벽하게 풀었다...!!
한번에 푼건 너무 기분이 좋다.. ㅎㅎ
그만큼 세부 조건들과 파악하지 않아도 될 조건들을 바로 떠올린 것 같다.
풀이
DFS로 풀었고, BFS였어도 방식은 똑같았을 것이다.
(큐를 사용하는 것 제외)
이번에는 원본을 훼손하면 안되기 떄문에,
bool Visited를 사용하였고 방문표시를 하였다.
변수 입력을 제외한 main의 코드는 위와 같다.
t라는 높이마다 반복하는 for문 내에 집어넣었다.
섬의 개수를 t마다 계산하며, maxIsland보다 크다면 갱신한다.
그리고 섬으로 방문하지 않은 좌표값이라면, DFS에 넣고
섬 땅덩이를 모조리 방문 표시해둔다.
그리고 모두 돌았는데도 섬이 하나도 없다면,
t를 바탕으로 한 for문을 종료한다.
그 이유는, 현재 수위에서도 모두 잠긴건데, 더 높아져도 모두 잠길 것이기 때문이다.
DFS문은 아주 평범하다.
조건에 맞으면 방문표시한다. DFS에 넣는다. 끝
이전문제에서도 겪은 일이지만..
여기서도 혹시 몰라서 DFS에 넣기 전에 방문표시를 해두었다.
한번에 정확한 문제의 의도를 간파하고,
조건을 정확히 설정했다는게 뿌듯하고,
약점이었던 좌표값을 어느정도 극복했다고 생각한다.
4. 2583 - DFS / 2D
https://www.acmicpc.net/problem/2583
2D 중에도 어려운 2D에 속하는 문제로 보인다.
그 이유는 원래는 칸의 좌표만 생각하면 되었는데,
이번에는 실제 좌표값을 사용하기도 하고,
두 좌표의 범위값을 사용해야하기도 한다.
구현해보자.
해결
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2
먼저 제대로 입력이 되는지 출력부터 해보았다.
잘된다.
그래프를 만들었으니 DFS만 진행하면 된다.
#include <iostream>
#include <cstring>
using namespace std;
int N, M, K;
void DFS(int, int);
int map[100][100];
int count = 0;
int sum[5000] = {
0,
};
int dx[4] = {0, -1, 0, 1}; // 위왼아오
int dy[4] = {1, 0, -1, 0};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> M >> N; // M이 세로, N이 가로
cin >> K;
memset(map, 0, sizeof(map));
// 사각형 좌표값에 따른 그래프 그리기
int ax, ay, bx, by;
for (int k = 0; k < K; k++)
{
cin >> ax >> ay;
cin >> bx >> by;
for (int x = ax; x < bx; x++)
{
for (int y = ay; y < by; y++)
{
map[y][x] = 1;
// cout << "x:" << x << " y:" << y << "\n";
}
}
}
// DFS
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (map[j][i] == 0)
{
map[j][i] = 1; // visited
DFS(i, j);
count++;
}
}
}
//출력
cout << count << "\n";
// Bubble Sort
for (int i = 0; i < count; i++)
{
for (int j = 0; j < count - i - 1; j++)
{
if (sum[j] > sum[j + 1])
{
int tmp = sum[j + 1];
sum[j + 1] = sum[j];
sum[j] = tmp;
}
}
}
for (int i = 0; i < count; i++)
{
cout << sum[i] << " ";
}
return 0;
}
void DFS(int x, int y)
{
sum[count]++;
for (int i = 0; i < 4; i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if (cx < 0 || cy < 0 || cx >= N || cy >= M)
{
continue;
}
else
{
if (map[cy][cx] == 0)
{
map[cy][cx] = 1; // visited
DFS(cx, cy);
}
}
}
}
실버수준은 마스터한 것 같다.
풀이
여태 DFS문제와 비슷하지만, 다른점은 map을 좌표값에 따라 그려야한다는 것이다.
그리기만하면, DFS를 하면 끝.
골드까지 가보자
