1. 알고리즘 문제 해결
벽 부수고 이동하기2(백준 14442):
로직 자체는 쉽게 떠올릴 수 있는데, 구현하는 과정에서 조금 섬세해야하는 문제. 최단경로 문제인데, 인접정보보단 행렬자체가 주어지는데다 벽을 부수는 것 때문에 타 알고리즘보다 BFS가 적합하다.
방문처리를 할 때 현재 부순 벽의 수 별로 따로 처리해주는 것만 신경쓰면, 다른 BFS 최단 경로 찾기와 같다. 나는 현재까지의 경로 길이를 방문 처리할 때 이용했는데, BFS의 특성상 굳이 그렇게 안하고 방문 여부만 이용했어도 괜찮았을 것 같다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std ;
int dx [ 4 ] = { 1 , 0 , - 1 , 0 };
int dy [ 4 ] = { 0 , 1 , 0 , - 1 };
int n , m ;
vector < vector < bool > > matrix ;
vector < vector < vector < int > > > isVisited ;
bool isValid ( int y , int x ) {
return ( y >= 0 && y < n && x >= 0 && x < m );
}
int main () {
cin . tie ( nullptr );
ios_base :: sync_with_stdio ( false );
int k ;
cin >> n >> m >> k ;
matrix = vector < vector < bool > > ( n , vector < bool >( m , false ));
isVisited = vector < vector < vector < int > > > ( n , vector < vector < int > >( m , vector < int >( k + 1 , - 1 )));
for ( int i = 0 ; i < n ; i ++) {
string s ;
cin >> s ;
for ( int j = 0 ; j < m ; j ++) {
matrix [ i ] [ j ] = s [ j ] - '0' ;
}
}
queue < pair < pair < int , int >, pair < int , int > > > q ;
q . push ({{ 0 , 0 }, { 1 , 0 }});
while (! q . empty ()) {
pair < int , int > curP = q . front (). first ;
pair < int , int > curInfo = q . front (). second ;
q . pop ();
if ( isVisited [ curP . first ] [ curP . second ] [ curInfo . second ] !=- 1 && isVisited [ curP . first ] [ curP . second ] [ curInfo . second ] <= curInfo . first ) continue ;
if ( curP . first == n - 1 && curP . second == m - 1 ) {
cout << curInfo . first ;
return 0 ;
}
isVisited [ curP . first ] [ curP . second ] [ curInfo . second ] = curInfo . first ;
for ( int i = 0 ; i < 4 ; i ++) {
int ny = curP . first + dy [ i ];
int nx = curP . second + dx [ i ];
if ( isValid ( ny , nx )) {
if ( matrix [ ny ] [ nx ] ) {
if ( curInfo . second < k && ( isVisited [ ny ] [ nx ] [ curInfo . second + 1 ] ==- 1 || isVisited [ ny ] [ nx ] [ curInfo . second + 1 ] > curInfo . first + 1 )) {
q . push ({{ ny , nx },{ curInfo . first + 1 , curInfo . second + 1 }});
}
} else {
if ( isVisited [ ny ] [ nx ] [ curInfo . second ] ==- 1 || isVisited [ ny ] [ nx ] [ curInfo . second ] > curInfo . first + 1 ) {
q . push ({{ ny , nx },{ curInfo . first + 1 , curInfo . second }});
}
}
}
}
}
cout << "-1" ;
}
달이 차오른다, 가자.(백준 1194):
위 문제와 비슷한 맥락으로, BFS로 접근하되 방문처리를 각 열쇠의 보유 여부에 따라 나누어 처리해주기로 했다. 그리고 특정 요소들에 대한 방문여부나 선택여부 등을 가장 효과적으로 나타낼 수 있는 것은 아마 비트마스킹일 것이다. 연산 속도면에서나 차지하는 공간 면에서나 쓰지 않을 이유가 없다.
탐색하려는 곳이 문인 경우, 필요한 열쇠가 있는지 먼저 확인하고 방문 여부를 확인한다. 이 때 문과 열쇠는 각각 문자-'A' 혹은 문자-'a'만큼 1을 left shift한 값을 취함으로 각각 대응될 수 있도록 한다. 열쇠 보유 여부는 비트단위 and 연산으로 간단하게 확인할 수 있다.
탐색하려는 곳이 열쇠일 경우, 비트단위 or 연산을 통해 열쇠를 획득했음을 표현해줄 수 있다. 이전에 보유했던 열쇠여도 or 연산이기 때문에 열쇠 보유 상태는 올바르게 표현된다. 이 열쇠 보유 상태를 기반으로 방문 여부를 확인해준다.
탐색하려는 곳이 문, 열쇠, 벽도 아닌 경우, 평범하게 현재의 열쇠 보유 상태를 그대로 이용해 방문 여부를 확인해준다.
이 과정을 통해 BFS를 지속하며 도착한 곳이 '1'이라면 그 때 가지고 있던 현재까지의 길이 값을 출력하고 return으로 함수를 종료해준다. BFS를 위한 while 루프 아래에는 -1을 출력하도록 해두면, BFS를 통해 미로를 탈출하지 못 할 경우 도달할 것이다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std ;
int dx [ 4 ] = { 1 , 0 , - 1 , 0 };
int dy [ 4 ] = { 0 , 1 , 0 , - 1 };
int n , m ;
vector < vector < char > > matrix ;
vector < vector < vector < bool > > > isVisited ;
bool isValid ( int y , int x ) {
return ( y >= 0 && y < n && x >= 0 && x < m );
}
bool isUpperCase ( char c ) {
return c >= 'A' && c < 'G' ;
}
bool isLowerCase ( char c ) {
return c >= 'a' && c < 'g' ;
}
int main () {
cin . tie ( nullptr );
ios_base :: sync_with_stdio ( false );
cin >> n >> m ;
matrix = vector < vector < char > > ( n , vector < char >( m ));
isVisited = vector < vector < vector < bool > > > ( n , vector < vector < bool > >( m , vector < bool >( 1 << 6 , false )));
pair < int , int > start ;
for ( int i = 0 ; i < n ; i ++) {
for ( int j = 0 ; j < m ; j ++) {
cin >> matrix [ i ] [ j ] ;
if ( matrix [ i ] [ j ] == '0' ) {
start = { i , j };
}
}
}
queue < pair < pair < int , int >, pair < int , int > > > q ;
q . push ({ start , { 0 , 0 }});
while (! q . empty ()) {
pair < int , int > curP = q . front (). first ;
pair < int , int > curInfo = q . front (). second ;
q . pop ();
if ( isVisited [ curP . first ] [ curP . second ] [ curInfo . second ] ) continue ;
if ( matrix [ curP . first ] [ curP . second ] == '1' ) {
cout << curInfo . first ;
return 0 ;
}
isVisited [ curP . first ] [ curP . second ] [ curInfo . second ] = true ;
for ( int i = 0 ; i < 4 ; i ++) {
int ny = curP . first + dy [ i ];
int nx = curP . second + dx [ i ];
if ( isValid ( ny , nx )) {
if ( isUpperCase ( matrix [ ny ] [ nx ] )) {
if (( curInfo . second & 1 << matrix [ ny ] [ nx ] - 'A' ) && ! isVisited [ ny ] [ nx ] [ curInfo . second ] ) {
q . push ({{ ny , nx }, { curInfo . first + 1 , curInfo . second }});
}
} else if ( isLowerCase ( matrix [ ny ] [ nx ] )) {
int nMask = curInfo . second | 1 << matrix [ ny ] [ nx ] - 'a' ;
if (! isVisited [ ny ] [ nx ] [ nMask ] ) {
q . push ({{ ny , nx }, { curInfo . first + 1 , nMask }});
}
} else if ( matrix [ ny ] [ nx ] != '#' && ! isVisited [ ny ] [ nx ] [ curInfo . second ] ) {
q . push ({{ ny , nx }, { curInfo . first + 1 , curInfo . second }});
}
}
}
}
cout << "-1" ;
}
