BOJ 3197 백조의 호수(C++)

castle_ticket·2022년 9월 28일
알고리즘

백조의 호수

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 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..... .................
처음 첫째 날 둘째 날
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

어쩌면 이 문제의 핵심은 지켜봐야하는 객체가 3개라는 점이다. 물/빙판/백조 모두 BFS 를 사용하여 update 하며 코드를 진행시켜야한다. 근데 update 를 어떻게 할까? -> 시간이 충분하면 이 전에 풀었던 [안전영역] 문제처럼 그래프를 카피하면서 진행시켜도 될 일이다. 하지만 여기서의 조건은 1500 이다 절대 1초 안에 들어올 수없다. 그렇다면 어떻게 문제를 해결할까? 중간을 말해요 에서 우선순위 큐를 2개 사용해서 중간 값을 찾았던 문제가 있다. 이 문제 또한 큐를 여러개 사용해서 BFS를 단 한번 사용하고 방문 했던 곳은 다시 방문하지 않는다. 라는게 컨셉이다. 코딩테스트에서 문제를 해결할때 뭔가 했던 일을 반복적으로 하는 느낌이 나면 대부분 시간 초과이다. ((https://velog.io/@castleticket/boj2468))

key point (참고 내용)

3-1) 백조에 대한 BFS()  

  • 백조가 다른 백조를 찾기 위해서 인접한 방향으로 나아갈 때    
    인접한 방향이 물이라면 : 현재 Queue에 Push후 계속 진행.    
    인접한 방향이 빙판이라면 : 백조의 Next Queue에 Push후 진행.    
    인접한 방향이 백조라면 : 서로 만났다는 것을 Check 해준 후 종료.    
    이렇게 3가지에 대해서 구현해 주면 된다.이 때, 일반적인 BFS와 같이 이미 탐색한 정점에 대해서는 다시 탐색하는 일이 없도록 Visit배열에 Check는 해줘야 한다.  

3-2) 물에 대한 BFS()  

  • 본인은 초기에 맵을 입력 받을 때, 빙판이 아닌 지점에 대해서는 모두 물에 대한 Queue에 모두 push해 주었다. 여기서 빙판이 아닌 지점에 대해서 모두 넣은 이유는, 빙판 근처에 물이 있거나 백조가 있더라도, 그 빙판은 녹기 때문이다. 쉽게 생각해서 물인 지점에 대해서 Queue에 모두 넣어주었다고 생각하고 접근하자.  

  • 물인 지점에서 인접한 방향으로 나아갈 때    
    인접한 방향이 빙판이라면 : 물의 Next Queue에 push후 진행 & 해당 정점을 물로 바꿔주기.     이 부분에 대해서만 구현을 해주면 된다.
    출처: https://yabmoons.tistory.com/64 [얍문's Coding World..:티스토리]

시간초과 코드

아래 방법이 가장 대중적이지 않을까 싶다,,

int r, c;
char board[1501][1501];
int visited[1501][1501];
int answer = 0;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
std::vector<std::pair<int, int> >v; // 0 : start , 1 : end
void input()
{
	std::cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			std::cin >> board[i][j];
			if (board[i][j] == 'L')
			{
				v.push_back({ i,j });
			}
		}
	}
}
bool canMeeting()
{
	std::queue<std::pair<int, int>> q;
	memset(visited, 0, sizeof(visited));
	q.push({v[0].first, v[0].second});
	int target_x = v[1].first;
	int target_y = v[1].second;

	while (!q.empty())
	{
		int x, y;
		x = q.front().first;
		y = q.front().second;
		q.pop();

		if (x == target_x && y == target_y)
		{
			return true;
		}

		for (int i = 0; i < 4; i++)
		{
			int nx, ny; 
			nx = x + dx[i];
			ny = y + dy[i];

			if (nx < 0 || nx > r || ny < 0 || ny > c || board[nx][ny] == 'X') continue;

			if (visited[nx][ny] == 0 && (board[nx][ny] == '.' || board[nx][ny] =='L') )
			{
				visited[nx][ny] = 1;
				q.push({ nx,ny });


			}
			
		}
	}

	return false;

	

}
void meltingIce()
{

	for (int x = 0; x < r; x++)
	{
		for (int y = 0; y < c; y++)
		{
			if (board[x][y] == '.')
			{
				// 여기를 기점으로 녹여보자!
				for (int i = 0; i < 4; i++)
				{
					int nx, ny;
					nx = x + dx[i];
					ny = y + dy[i];

					if (nx < 0 || nx > r || ny < 0 || ny > c) continue;
					if (board[nx][ny] == 'X')
					{
						board[nx][ny] = 'D';
					}

				}

			}
		}
	}

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (board[i][j] == 'D')
			{
				board[i][j] = '.';
			}
		}
	}
	

}

int main()
{
	input();
	

	while(true)
	{
		if (canMeeting())
		{
			break;
		}
		meltingIce();
		answer += 1;

	}

	std::cout << answer << std::endl;
	
}

어디를 어떻게 개선했고, 어떤 점에서 틀렸는지 살펴보자.
먼저 백조 두마리가 만날 수 있는 BFS 코드이다.

여기서 가장 큰 문제는 매번 q를 선언해서 시작점을 넣어주고 계속 반복적으로 BFS 를 한다는 점이다.
함수를 반복적으로 호출하여 방문 배열을 초기화하고 BFS 탐색을 한다.(누가봐도 조금 이상,,)
memset(visited, 0, sizeof(visited));

Before

bool canMeeting()
{
	std::queue<std::pair<int, int>> q;
	memset(visited, 0, sizeof(visited));
	q.push({v[0].first, v[0].second});
	int target_x = v[1].first;
	int target_y = v[1].second;

	while (!q.empty())
	{
		int x, y;
		x = q.front().first;
		y = q.front().second;
		q.pop();

		if (x == target_x && y == target_y)
		{
			return true;
		}

		for (int i = 0; i < 4; i++)
		{
			int nx, ny; 
			nx = x + dx[i];
			ny = y + dy[i];

			if (nx < 0 || nx > r || ny < 0 || ny > c || board[nx][ny] == 'X') continue;

			if (visited[nx][ny] == 0 && (board[nx][ny] == '.' || board[nx][ny] =='L') )
			{
				visited[nx][ny] = 1;
				q.push({ nx,ny });


			}
			
		}
	}

	return false;
   
    }
}

After

백조의 시작점을 시작으로 '.' 물은 당연히 방문처리하고 백조 큐에 넣어주고, 물과 인접한 X는 다음 백조가 방문해야할 지점 임으로 방문 예정 큐에 넣어준다. 이렇게 하면 뭐가 좋을까? 그렇다면 백조가 사실상 방문 예정 큐 부터 시작한다고 볼 수 있다. 이전 방문 대상들은 모두 visited[nx][ny] = 1; 처리 해줬고, x도 방문 예정임으로 1로 수정해주면 다음은 x를 기준으로 상하좌우 중 방문 가능한 장소를 queue에 넣어준다.
이렇게 되면 방문 배열을 매번 초기화하지 않아도 되고 누적해서 탐색이 가능하다. 큐를 2개써서 다음 방문할 장소에 대한 큐를 컨트롤한 다는 점이 이 문제의 핵심이다.

bool sawn_bfs()// swan bfs
{


	while (!sq.empty())
	{
		int x, y;
		x = sq.front().first;
		y = sq.front().second;
		sq.pop();

		if (x == target_x && y == target_y)
		{
			return true;
		}

		for (int i = 0; i < 4; i++)
		{
			int nx, ny;
			nx = x + dx[i];
			ny = y + dy[i];

			if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;

			if (visited[nx][ny] == 0)
			{
				if (g_map[nx][ny] == '.' || g_map[nx][ny] == 'L')
				{
					visited[nx][ny] = 1;
					sq.push({ nx, ny });
				}

				if (g_map[nx][ny] == 'X' )
				{
					visited[nx][ny] = 1;
					snq.push({ nx,ny }); // 
				}
			}
			
		}


	}

	return false;

}

Before

얼음을 녹여주는 코드를 보자
이전 코드는 단순하게 '.'으로부터 인접한 X를 임시 char -> D로 바꾸고
D-> '.'으로 바꿔주는 코드 이다. 임시로 D->로 바꾸는 이유는 '.'으로 바꾸면 한 큐에 전부 다 녹아 버린다..

void meltingIce()
{

	for (int x = 0; x < r; x++)
	{
		for (int y = 0; y < c; y++)
		{
			if (board[x][y] == '.')
			{
				// 여기를 기점으로 녹여보자!
				for (int i = 0; i < 4; i++)
				{
					int nx, ny;
					nx = x + dx[i];
					ny = y + dy[i];

					if (nx < 0 || nx > r || ny < 0 || ny > c) continue;
					if (board[nx][ny] == 'X')
					{
						board[nx][ny] = 'D';
					}

				}

			}
		}
	}

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (board[i][j] == 'D')
			{
				board[i][j] = '.';
			}
		}
	}

After

물을 따로 BFS를 이용한 탐색 작업을 해준다. 물은 간단하다. 처음 input시에 물 Queue에 물 좌표를 큐에 넣어두고, 물과 인접한 'X'는 다음에 물이 될 큐에 넣어주고 해당을 맵에 'X'를 '.'로 바꿔준다 그래야 다시 위로 올라가서 백조 BFS 시에 '.'을 방문할 수 있기 때문이다.


void water_bfs()
{

	while(!wq.empty())
	{
		int x, y;
		x = wq.front().first;
		y = wq.front().second;
		wq.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx, ny;
			nx = x + dx[i];
			ny = y + dy[i];

			if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;

			if (g_map[nx][ny] == 'X')
			{
				g_map[nx][ny] = '.';
				wnq.push({ nx,ny });
			}
			
		}

	}
	
}

Main

이 후 메인에서는 지금 기준으로 next 라고 생각했던 백조는 current로 바뀌고 다음 물이 되어야 했던 queue도 current 물 queue로 이전하고 next queue들은 전부 pop 해준다 (중복 방지) 이렇게 되면 결국 2개의 BFS 처럼 보이지만 사실은 잘보면 하나의 BFS 동작은 분할 한것 뿐이다. 이유는 중복 방문을 하지 않기 위함이다. q를 여러개 사용하여 문제를 해결할 수 있다는 점을 아이디어로 가져가면 될 것 같다.


	while (true)
	{
		if (sawn_bfs())
		{
			break;
		}
		water_bfs();
		sq = snq;
		wq = wnq;
		
		while (!snq.empty()) snq.pop();
		while (!wnq.empty()) wnq.pop();
		answer += 1;

	}
profile
castle_ticket
나만의 개발 공책
이전 포스트

BOJ 2468 안전 영역(C++)

다음 포스트

BOJ 7579 앱 (C++)

0개의 댓글