2024 - 09- 25 C++ 코딩테스트 10주완성 D+41
백준 3179 문제 - 백조의 호수
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다.
두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
...XXXXXX..XX.XXX ....XXXX.......XX .....XX..........
....XXXXXXXXX.XXX .....XXXX..X..... ......X..........
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X.....
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX....
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX....
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............
..XXXXX...XXX.... ....XX.....X..... .................
....XXXXX.XXX.... .....XX....X..... .................
처음 첫째 날 둘째 날
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 R과 C가 주어진다. (단, 1 ≤ R, C ≤ 1500)
다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다.
'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
출력
첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
실습코드
#include <bits/stdc++.h>
using namespace std;
//1. 변수목록
//호수의 행과 열의 정보를 받을 정수형 변수 R,C o
//방문한 곳의 정보를 표기할 2차원 정수 행렬 visited o
//호수의 정보를 담을 2차원 문자열 행렬 lake o
//상하좌우로 이동할 정보를 담을 배열 dy[4] = {-1,0,1,0} , dx[4] = {0,1,0,-1}; o
//백조 두마리의 위치값을 저장할 Vector<pair<int,int>> Lpos
//호수 바로옆에 있는 얼음의 위치를 담을 queue<pair<int,int>> icepos
//호수의 위치를 담을 queue<pair<int,int>> lakepos
//탐색 시작위치의 정보를 담을 정수형 변수 y,x o
//다른 백조를 찾았을 때를 표시하기 위한 bool형 변수 isFind = false;
//걸리는 날을 카운트할 정수형 변수 cnt o
const int max_n = 1504;
int R,C,cnt,y,x;
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};
char lake[max_n][max_n];
int visited[max_n][max_n];
queue<pair<int,int>> icepos;
vector<pair<int,int>> Lpos;
bool isFind = false;
//2-3-1. dfs(y,x)
//2-3-1-1. visited[y][x] = 1;
//2-3-1-2. for(int i =0; i < 4; i++)
//2-3-1-3. int ny = y + dy[i];
//2-3-1-4. int nx = x + dx[i];
//2-3-1-5. if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue;
//2-3-1-6. if(ny == Lpos[1].front() && nx == Lpos[1].second()) isFind = true; cout << cnt; return;
//2-3-1-7. if(a[ny][nx] == '.') dfs(ny,nx);
//2-3-1. dfs(y,x) 종료
void dfs(int y,int x)
{
visited[y][x] = 1;
for(int i=0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
pair<int,int> dst = make_pair(ny,nx);
if(ny < 0 || ny >= R || nx < 0 || nx >= C || visited[ny][nx]) continue;
if((dst == Lpos[0] || dst == Lpos[1]) && !isFind)
{
isFind = true;
return;
}
if(lake[ny][nx] == 'X')
{
icepos.emplace(ny,nx);
}
else if(lake[ny][nx] == '.') dfs(ny,nx);
}
}
int main()
{
//2. 알고리즘
//2-1. R과 C를 입력받는다.
//2-2. R만큼 반복문
//2-2-1. C만큼 반복문
//2-2-1-1. lake[i][j] 안에 값을 입력받는다.
//2-2-1-2. 만약 lake[i][j] 의 값이 L일 경우,Lpos.push_back{i,j};
//2-2-1. C만큼 반복문 종료
//2-2. R만큼 반복문 종료
cin >> R >> C;
for(int i =0; i < R; i++)
{
string str = "";
cin >> str;
for(int j =0; j < str.size(); j++)
{
lake[i][j] = str[j];
if(str[j] == 'L') Lpos.emplace_back(i,j);
}
}
//2-3. while(!isFind)
//2-3-2. cnt++;
while(!isFind)
{
memset(visited,0,sizeof(visited));
for(pair<int,int> a : Lpos)
{
y = a.first;
x = a.second;
if(!isFind) dfs(y,x);
}
if(isFind)
{
cout << cnt;
break;
}
else cnt++;
while(icepos.size())
{
pair<int,int> a = icepos.front(); icepos.pop();
lake[a.first][a.second] = '.';
}
}
return 0;
}
지금 짠 코드의 로직은 DFS 탐색이다. DFS 탐색을 하여 L 과 L 을 찾으러 다니면서, X를 만나면 스택에다가 추가하고
만약 L끼리 서로 만나지 못하면, 일수를 세는 변수인 Cnt를 증감하여주고, 스택에다가 추가한 X를 물을 나타내는 문자인
' . ' 으로 바꿔주고 다음 한 바퀴를 돈다.
이렇게하여서 L끼리 만나면 Cnt를 출력시켜주는 방식으로 로직을 구성하여서 테스트 케이스 3개까지 다 통과하였는데..
두구두구 결과는..!
시간초과이다 ㅎㅎ. 열과 행의 최대범위가 각 1500이니까 DFS 탐색으로 돌려도 괜찮을 줄 알았는데.. 뭐가 문젠지 잘 모르겠다.
강의실습코드를 보고 분석해보자.
#include <bits/stdc++.h>
using namespace std;
const int max_n = 1501;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int visited_swan[max_n][max_n], visited[max_n][max_n], R, C, day, swanY, swanX, y, x;
char a[max_n][max_n];
queue<pair<int, int>> waterQ, water_tempQ, swanQ, swan_tempQ;
string s;
void Qclear(queue<pair<int, int>> &q){
queue<pair<int, int>> empty;
swap(q,empty);
}
void water_melting(){
while(waterQ.size()){
tie(y, x) = waterQ.front();
waterQ.pop();
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= R || nx < 0 || nx >= C || visited[ny][nx])continue;
if(a[ny][nx] == 'X'){
visited[ny][nx] = 1;
water_tempQ.push({ny, nx});
a[ny][nx] = '.';
}
}
}
}
bool move_swan(){
while(swanQ.size()){
tie(y, x) = swanQ.front();
swanQ.pop();
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= R || nx < 0 || nx >= C || visited_swan[ny][nx])continue;
visited_swan[ny][nx] = 1;
if(a[ny][nx] == '.')swanQ.push({ny, nx});
else if(a[ny][nx] == 'X') swan_tempQ.push({ny, nx});
else if(a[ny][nx] == 'L') return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> R >> C;
for(int i = 0; i < R; i++){
cin >> s;
for(int j = 0; j < C; j++){
a[i][j] = s[j];
if(a[i][j] == 'L'){swanY = i; swanX = j;}
if(a[i][j] == '.' || a[i][j] == 'L')visited[i][j] = 1, waterQ.push({i, j});
}
}
swanQ.push({swanY, swanX});
visited_swan[swanY][swanX] = 1;
while(true){
if(move_swan()) break;
water_melting();
waterQ = water_tempQ;
swanQ = swan_tempQ;
Qclear(water_tempQ);
Qclear(swan_tempQ);
day++;
}
cout << day << "\n";
return 0;
}
이 로직은 Bfs 탐색으로 구성되었다.
먼저 호수의 정보를 입력받을때 백조의 위치 swanY 와 swanX 를 입력받고,
물 또는 백조인 경우에는 물을 담는 스택인 waterQ에 해당좌표를 push 시켜준다.
입력이 끝나고, 아까 입력받은 백조의 위치 swanY 와 swanX를 swanQ 안에 push 시켜주고 해당위치에서 부터 시작하므로,
visited_swan[swanY][swanX] = 1; 을 해준다.
move_swan 함수는
백조끼리 만날 수 있는 지 확인하고 만약 만난다면 해당 일자를 출력시켜주고, 만나지 않는다면
물을 이동시켜서, 물 근처에 있는 얼음을 찾아 얼음의 위치는 담는 swan_tempQ에 push를 시켜주는 함수이다.
water_melting 함수는
말 그대로 swan_temQ 에 입력시켜놨던 얼음을 물로 해동시켜주는 함수이다.
스택안에 있는 얼음의 위치를 따와 물을 의미하는 문자열인 ' . ' 로 바꿔준다.
그리고 두개의 함수가 끝나면 얼음이 해동되었으므로 일자를 의미하는 day 를 증감하여준다.
이 알고리즘의 핵심은 두개의 visited 배열을 이용하여
맨 처음 물근처의 얼음을 탐색하고 Cnt를 증감하여준 다음에, 다음 탐색위치를 해동시킨 얼음의 위치부터 시작한다는 것이다.
이러면 내가 풀었던 시간복잡도보다 훨씬 더 효율적이게 된다.
아직 bfs 길은 멀고도 힘들구나..