[baekjoon] 3197번 : 백조의 호수 (C++)

[baekjoon] 3197번 : 백조의 호수 (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..... ................. 처음 첫째 날 둘째 날

이건 BFS 문제이다

BFS (Breath-First search)

- L과 L 사이에 경로가 존재하는지 판별하고, 경로가 없다면 하루가 지나 얼음이 녹은 상태에서 다시 탐색

- 반복문을 통해 길을 찾을때까지 반복한다면 시간초과

BFS는?

1. L(시작노드) 방문

- 방문한 노드 큐에 삽입

2. 큐에서 꺼낸 노드와 인접한 노드를 차례로 방문

- 큐에서 꺼낸 노드 방문(인접한 노드가 없다면 큐의 front에서 노드 꺼냄)

- 큐에 방문한 노드 삽입

3. 큐가 소진될 때까지 계속

이걸 이 문제에 적용한다면

1. 먼저 둘 중 하나의 L 주변에 있는 물을 BFS로 탐색

2. 다른 L을 찾을 수 없었다면 물 옆의 얼음을 nextQ에 삽입

3. 얼음을 녹임(하루 지남)

4. 그렇다면 nextQ에는 L이 둘러볼 물이 남음(이전에 탐색한 물을 재탐색할 필요 X)

- waterQ를 생성해 물을 저장해놓고, 얼음을 녹이는 방식도 있음

[코드]

// BOJ 3197번 : 백조의 호수 #include #include using namespace std; struct Queue{ // 좌표 2개로 이루어진 큐 int x; int y; }; char lake[1501][1501]; // 호수 char visit[1501][1501]; // 방문 표시 배열 int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int main() { int r, c; // 호수의 행, 열 int lr, lc; // L의 위치 string s; // 호수 받기 int day = 0; // 걸리는 날 queue waterQ; // 물인 곳을 넣는 큐 cin >> r >> c; // 먼저 행과 열을 입력받음 for(int i = 0; i < r; i++){ cin >> s; // 문자열 입력받음(줄 단위) for(int j = 0; j < c; j++){ lake[i][j] = s[j]; // 입력받은 문자를 호수 배열에 대입 if(lake[i][j] == 'L'){ // 만약 L이라면 lr = i; // L의 위치를 저장 lc = j; } if(lake[i][j] == '.' || lake[i][j] == 'L'){ waterQ.push({i, j}); // 물이라면 waterQ에 push } } } queue Q; Q.push({lr, lc}); // L의 위치를 push visit[lr][lc] = true; // L의 위치 방문했다고 체크 while(1){ queue nextQ; bool success = false; while(!Q.empty() && !success){ // 큐가 비어있지 않고, 성공하지 않을경우 반복 auto temp = Q.front(); Q.pop(); for(int i = 0; i < 4; i++){ // 현재 위치에서 주위 탐색하는 것(상하좌우) int nx = temp.x + dx[i]; // 다음 탐색할 x int ny = temp.y + dy[i]; // 다음 탐색할 y if(nx < 0 || nx > r - 1 || ny < 0 || ny > c - 1) // 범위 벗어난 경우 continue; if(lake[nx][ny] == 'L' && visit[nx][ny] == false){ // L인데 방문 X success = true; // 탐색 성공 break; // 반복문 종료 } if(lake[nx][ny] == '.' && visit[nx][ny] == false){ // 물인데 방문 X Q.push({nx, ny}); // 큐에 위치 넣음 visit[nx][ny] = true; // 방문했다고 표시 } if(lake[nx][ny] == 'X' && visit[nx][ny] == false){ // 얼음인데 방문 X nextQ.push({nx, ny}); // 다음에 방문하기 위해 nextQ에 push visit[nx][ny] = true; // 방문했다고 표시 } } } if(success){ // 탐색 성공시 cout << day << "

"; // 걸린 날짜 출력 break; // while문 종료 } Q = nextQ; // 큐에 방문해야 할 nextQ를 넣음 int watersize = waterQ.size(); // waterQ의 원소 개수 while(watersize){ // 하루가 지나 얼음이 녹은 상황으로 바꿔줌 auto temp = waterQ.front(); // waterQ의 맨 앞 원소 담음 waterQ.pop(); // 담은 원소 제거 for(int i = 0; i < 4; i++){ // 상하좌우 탐색 시작 int nx = temp.x + dx[i]; int ny = temp.y + dy[i]; if(nx < 0 || nx > r - 1 || ny < 0 || ny > c - 1) // 범위 벗어난 경우 continue; if(lake[nx][ny] == 'X'){ // 얼어있는 경우 waterQ.push({nx, ny}); // 위치 저장하고(push) lake[nx][ny] = '.'; // 물로 바꿈 } } watersize--; } day++; // 하루 증가 } }

여기서 auto란? → 타입 추론

- auto 키워드는 선언된 변수의 초기화 식을 사용해 해당 형식을 추론하도록 컴파일러에 지시

- 즉 초깃값의 형식에 맞춰 선언하는 인스턴스(변수)의 형식이 '자동'으로 결정 → 타입 추론(type inference)

실행결과

from http://kwonjeong.tistory.com/14 by ccl(A) rewrite - 2021-09-09 19:00:50