3197 백조의 호수
알고리즘(구현)
처음 방법
1. 한 백조에서 BFS 실시하여 다른 백조를 만날 수 있는지 검사
2. 전체 맵을 검사해서 녹일 수 있는 걸 녹임
3. day 추가하고 다시 1부터
-> 시간이 너무 걸림. 특히 맵 초기화하는 부분이 많이 걸림
두번째 방법
1. 1번은 유지
2. 녹을 수 있는 얼음만 저장한 q에서 얼음을 하나씩 꺼내서 녹이고, 주변에 검사되지않은 얼음이 있으면 따로 저장
-> q가 끝나면 따로 저장한 얼음을 q에 복사
3. day추가하고 다시 1부터
-> 또 시간초과
세번째 방법
1. 백조가 갈수있는 칸을 전부 각각 L, l 로 바꿈
2. 얼음과 L, l의 경계선을 q에 저장
3. 2방법으로 다 녹이고 나서, q에 있는 칸을 하나씩 꺼내고 주변을 검사하여 또 L, l 로 바꾼다
4. 바꾸는데 다른 문자를 발견하면 스탑 후 출력
-> 코드가 너무 복잡하여 헷갈림. 어딘가 잘못됨
네번째 방법
1. 백조가 갈 수 잇는 칸을 전부 각각 L,l 로 바꿈
2. 얼음을 한칸 녹일 때마다 주변을 검사하여 적절한 문자로 치환
주변에 (L과 l) 두개 있을 때
-> 만난 것 -> 출력 후 종료
주변에 L 또는 l 만 있을 때
-> 만나지 않음. 그 얼음칸을 중심으로 BFS를 실시하여 갈 수 있는 모든 칸을 L 또는 l로 바꿈
주변에 L, l 둘다 없을 때
-> 그냥 . 으로 치환
-> 통과
코드
#include <iostream>
#include <vector>
#include <list>
#define MAX_WIDTH 1500
using namespace std ;
typedef struct Location {
int row;
int col;
} Location ;
int row, col, todayLength;
Location bird1, bird2;
Location meltToday[MAX_WIDTH * MAX_WIDTH];
char map[MAX_WIDTH][MAX_WIDTH];
bool visit[MAX_WIDTH][MAX_WIDTH], meltVisit[MAX_WIDTH][MAX_WIDTH];
list < Location > q;
bool init ();
void initBird ( Location bird , char c );
bool meltIce ();
bool checkBird ( int r , int c );
int main () {
ios :: sync_with_stdio ( 0 );
cin. tie ( 0 );
cout. tie ( 0 );
cin >> row >> col;
bool check = false ;
for ( int i = 0 ; i < row; i ++ ) {
for ( int j = 0 ; j < col; j ++ ) {
cin >> map[i][j];
if (map[i][j] == 'L' ) {
if ( ! check) {
bird1.row = i;
bird1.col = j;
check = true ;
}
else {
bird2.row = i;
bird2.col = j;
map[i][j] = 'l' ;
}
}
}
}
if ( init ()) {
cout << 0 ;
return 0 ;
}
int day = 1 ;
while ( true ) {
cout << endl;
for ( int i = 0 ; i < row; i ++ ) {
for ( int j = 0 ; j < col; j ++ )
cout << map[i][j];
cout << endl;
}
cout << endl;
if ( meltIce ()) {
cout << day;
break ;
}
day ++ ;
}
}
bool init () {
for ( int i = 0 ; i < row; i ++ ) {
for ( int j = 0 ; j < col; j ++ ) {
if (map[i][j] == 'X' ) {
if (i > 0 && map[i - 1 ][j] != 'X' ) {
meltToday[todayLength ++ ] = { i, j };
meltVisit[i][j] = true ;
}
else if (j < col - 1 && map[i][j + 1 ] != 'X' ) {
meltToday[todayLength ++ ] = { i, j };
meltVisit[i][j] = true ;
}
else if (i < row - 1 && map[i + 1 ][j] != 'X' ) {
meltToday[todayLength ++ ] = { i, j };
meltVisit[i][j] = true ;
}
else if (j > 0 && map[i][j - 1 ] != 'X' ) {
meltToday[todayLength ++ ] = { i, j };
meltVisit[i][j] = true ;
}
}
}
}
initBird (bird1, 'L' );
if (map[bird2.row][bird2.col] == 'L' )
return true ;
initBird (bird2, 'l' );
return false ;
}
void initBird ( Location bird , char c ) {
q. push_back ({ bird.row, bird.col });
visit[bird.row][bird.col] = true ;
while ( ! q. empty ()) {
Location temp = q. front ();
q. pop_front ();
map[temp.row][temp.col] = c;
if (temp.row > 0 && ! visit[temp.row - 1 ][temp.col] && map[temp.row - 1 ][temp.col] != 'X' ) {
q. push_back ({ temp.row - 1 , temp.col });
visit[temp.row - 1 ][temp.col] = true ;
}
if (temp.row < row - 1 && ! visit[temp.row + 1 ][temp.col] && map[temp.row + 1 ][temp.col] != 'X' ) {
q. push_back ({ temp.row + 1 , temp.col });
visit[temp.row + 1 ][temp.col] = true ;
}
if (temp.col > 0 && ! visit[temp.row][temp.col - 1 ] && map[temp.row][temp.col - 1 ] != 'X' ) {
q. push_back ({ temp.row, temp.col - 1 });
visit[temp.row][temp.col - 1 ] = true ;
}
if (temp.col < col - 1 && ! visit[temp.row][temp.col + 1 ] && map[temp.row][temp.col + 1 ] != 'X' ) {
q. push_back ({ temp.row, temp.col + 1 });
visit[temp.row][temp.col + 1 ] = true ;
}
}
}
bool meltIce () {
int index = 0 ;
vector < Location > q;
while (index < todayLength) {
if ( checkBird (meltToday[index].row, meltToday[index].col))
return true ;
if (meltToday[index].row > 0 && map[meltToday[index].row - 1 ][meltToday[index].col] == 'X' && ! meltVisit[meltToday[index].row - 1 ][meltToday[index].col] ) {
q. push_back ({ meltToday[index].row - 1 , meltToday[index].col });
meltVisit[meltToday[index].row - 1 ][meltToday[index].col] = true ;
}
if (meltToday[index].col < col - 1 && map[meltToday[index].row][meltToday[index].col + 1 ] == 'X' && ! meltVisit[meltToday[index].row][meltToday[index].col + 1 ]) {
q. push_back ({ meltToday[index].row, meltToday[index].col + 1 });
meltVisit[meltToday[index].row][meltToday[index].col + 1 ] = true ;
}
if (meltToday[index].row < row - 1 && map[meltToday[index].row + 1 ][meltToday[index].col] == 'X' && ! meltVisit[meltToday[index].row + 1 ][meltToday[index].col]) {
q. push_back ({ meltToday[index].row + 1 , meltToday[index].col });
meltVisit[meltToday[index].row + 1 ][meltToday[index].col] = true ;
}
if (meltToday[index].col > 0 && map[meltToday[index].row][meltToday[index].col - 1 ] == 'X' && ! meltVisit[meltToday[index].row][meltToday[index].col - 1 ]) {
q. push_back ({ meltToday[index].row, meltToday[index].col - 1 });
meltVisit[meltToday[index].row][meltToday[index].col - 1 ] = true ;
}
index ++ ;
}
todayLength = 0 ;
//넣기
for ( int i = 0 ; i < q. size (); i ++ )
meltToday[todayLength ++ ] = q[i];
return false ;
}
bool checkBird ( int r , int c ) {
bool checkL = false , checkl = false ;
if (r > 0 && map[r - 1 ][c] == 'L' )
checkL = true ;
else if (r < row - 1 && map[r + 1 ][c] == 'L' )
checkL = true ;
else if (c > 0 && map[r][c - 1 ] == 'L' )
checkL = true ;
else if (c < col - 1 && map[r][c + 1 ] == 'L' )
checkL = true ;
if (r > 0 && map[r - 1 ][c] == 'l' )
checkl = true ;
else if (r < row - 1 && map[r + 1 ][c] == 'l' )
checkl = true ;
else if (c > 0 && map[r][c - 1 ] == 'l' )
checkl = true ;
else if (c < col - 1 && map[r][c + 1 ] == 'l' )
checkl = true ;
if (checkL && checkl)
return true ;
else if (checkL) {
map[r][c] = 'L' ;
initBird ({ r,c }, 'L' );
if (map[bird2.row][bird2.col] == 'L' )
return true ;
}
else if (checkl) {
map[r][c] = 'l' ;
initBird ({ r,c }, 'l' );
if (map[bird1.row][bird1.col] == 'l' )
return true ;
}
else
map[r][c] = '.' ;
return false ;
}