Problem
Problem URL : 핀볼 게임
[1] Answer Code (18. 10. 20)
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
#define p pair<int,int>
using namespace std;
// 동 서 남 북
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*
(1,1)에서 동쪽(= 0)방향을 보고 있는데
(1,2)가 1번 모양이다.
그러면 (1,2)에서 진행해야하는 방향은 이제 서쪽(= 1)이 되야한다.
이걸 코드로 표현하면
changeDir[ i번 모양 ][ 현재 진행중 방향 ] // i번 모양 = 다음 위치에 있는 모양의 번호
changeDir[ 1 ][ 0 ] = 1;
*/
int changeDir[6][4] = {
{0,0,0,0}, // 빈 칸
{1,3,0,2}, // 1번 모양
{1,2,3,0}, // 2번 모양
{2,0,3,1}, // 3번 모양
{3,0,1,2}, // 4번 모양
{1,0,3,2} // 5번 모양
};
int maze[100][100];
int n;
int ans;
map<int,p> m;
bool inRange(int x, int y){
if(x < 0 || x >=n || y < 0 || y >= n)
return false;
return true;
}
int solve(int x, int y, int dir){
int cnt = 0;
int st_x = x;
int st_y = y;
int nx = x;
int ny = y;
while (1) {
nx += dx[dir];
ny += dy[dir];
if(! inRange(nx, ny)) { // Map을 벗어났다 = 방향 전환
cnt++;
/*
if ~ else if 구조가 아니면
if(dir == 0)에서 dir가 1로 바뀌고
if(dir == 1)에서 dir가 다시 0으로 바뀌는 대참사가 발생한다.
*/
if(dir == 0) dir = 1;
else if(dir == 1) dir = 0;
else if(dir == 2) dir = 3;
else if(dir == 3) dir = 2;
/*
만약 (-1,0)이 됐는데
continue가 없으면
그 아래 if 문에서
maze[-1][0]이 되는 대참사가 발생한다.
그렇기 때문에 반드시 continue가 필요하다.
*/
continue;
}
// 종료 : 블랙홀 or 시작점
if( maze[nx][ny] == -1 || (nx == st_x && ny == st_y) ){
break;
}
// 블록을 만날 경우
if( maze[nx][ny] >= 1 && maze[nx][ny] <=5 ){
cnt++;
dir = changeDir[ maze[nx][ny] ][dir];
}
// 웜홀을 만날 경우
if( maze[nx][ny] >= 6 && maze[nx][ny] <= 10){
int tmp_x;
int tmp_y;
/*
## 주의
[1] : nx = m[ maze[nx][ny] * 2].first;
[2] : ny = m[ maze[nx][ny] * 2].second;
이렇게 하면
nx = 1
ny = 1 이라고하면
[1]은 정상적인 값이 불러 오지만
[2]에 들어가는 nx 값은 1이 아니라 다른 값이 들어갈 수 있다.
그래서 tmp_x, tmp_y에 값을 저장하고
nx = tmp_x
ny = tmp_y 작업을 해준다.
*/
if( m[ maze[nx][ny] ].first == nx && m[ maze[nx][ny] ].second == ny){
tmp_x = m[ maze[nx][ny] * 2].first;
tmp_y = m[ maze[nx][ny] * 2].second;
}
else{
tmp_x = m[ maze[nx][ny] ].first;
tmp_y = m[ maze[nx][ny] ].second;
}
nx = tmp_x;
ny = tmp_y;
}
}
return cnt;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int TC;
cin >> TC;
for(int tc=1; tc<=TC; tc++){
memset(maze,0,sizeof(maze));
m.clear();
ans = -1;
cin >> n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> maze[i][j];
if(maze[i][j] >= 6 && maze[i][j] <= 10){
if(m.find(maze[i][j]) != m.end()){ // 이미 있는 경우
m[ maze[i][j] * 2 ] = m[ maze[i][j] ];
m[ maze[i][j] ] = p(i,j);
}
else{
m[ maze[i][j] ] = p(i,j);
}
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(maze[i][j] == 0){
for(int k=0; k<4; k++){
int _ans = solve(i,j,k);
ans = ans < _ans ? _ans : ans;
} // end of for k
} // end of if
} // end of for j
} // end of for i
cout << "#" << tc << " " << ans << '\n';
}
return 0;
}
Reivew
-
55분 소요
-
다시 푸는 문제였지만 후다닥 코딩은 실패했다.
-
그래도 큰 문제없이 해결했다.
-
신기한점은 예전에 풀었을 때 실수했던 부분을 똑같이 실수했다.
[2] Answer Code (18. 10. 14)
#include<iostream>
#include<map>
#define p pair<int,int>
using namespace std;
// 동서남북 순서
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int changeDir[6][4] ={
{0,0,0,0}, // 빈칸
{1,3,0,2},
{1,2,3,0},
{2,0,3,1},
{3,0,1,2},
{1,0,3,2}
};
int maze[100][100];
int n;
map<int,p> m;
bool inRange(int x, int y){
if( x < 0 || x >= n || y < 0 || y >= n)
return false;
return true;
}
int dfs(int x, int y, int dir){
int st_x = x;
int st_y = y;
int cnt = 0;
while (1) {
x = x + dx[dir];
y = y + dy[dir];
if(! inRange(x,y)){ // 범위 밖
dir = changeDir[5][dir];
cnt++;
}
else if(maze[x][y] == -1 || (x == st_x && y == st_y)){ // 블랙홀 or 시작점
return cnt;
}
else if(maze[x][y] == 0){ // 빈 공간
continue;
}
else if(maze[x][y] >= 1 && maze[x][y] <= 5){ // 벽일 경우
dir = changeDir[ maze[x][y] ][ dir ];
cnt++;
}
else{ // 웜홀일 경우
int tmp_x;
int tmp_y;
if( m[ maze[x][y] ] == p(x,y) ){
tmp_x = m[ maze[x][y] * 2 ].first;
tmp_y = m[ maze[x][y] * 2 ].second;
}
else{
tmp_x = m[ maze[x][y] ].first;
tmp_y = m[ maze[x][y] ].second;
}
x = tmp_x;
y = tmp_y;
}
} // end of while
return cnt;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int TC;
cin >> TC;
for(int tc=1; tc<=TC; tc++){
int ans = -1;
cin >> n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> maze[i][j];
if( maze[i][j] >= 6 && maze[i][j] <= 10){
if(m.find(maze[i][j]) != m.end()){ // 이미 웜홀 짝이 존재하는 경우
p pair_pos = m[ maze[i][j] ];
m[ maze[i][j] * 2 ] = pair_pos;
m[ maze[i][j] ] = p(i,j);
}
else{
m[ maze[i][j] ] = p(i,j);
}
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(maze[i][j] == 0){
for(int k=0; k<4; k++){ // 동서남북 방향 순서로 탐색
cout << i << " " << j << " " << k << endl;
int res = dfs(i,j,k);
ans = ans < res ? res : ans;
}
}
}
}
cout << "#" << tc << " " << ans << '\n';
}
return 0;
}
Review
-
어려웠다.
-
대칭으로 저장하는 작업이 생각보다 오래 걸렸다.
-
혼자서 해결하지 못하고 AC 코드를 보고 다시 풀었다.
-
내가 처음에 생각했던 구현보다 깔끔하고 명료해서 좋았다.
-
특히 방향에 대해서 한번에 표현하는 스킬이 신선했다.
int changeDir[6][4] ={
{0,0,0,0}, // 빈칸
{1,3,0,2},
{1,2,3,0},
{2,0,3,1},
{3,0,1,2},
{1,0,3,2}
};
- 처음에 생각했던 구현 방식에서 벽을 만나면 바로 좌표를 이동시켰는데 문제가 발생했다.
/*
## dir
0 : Right
1 : Bottom
2 : Left
3 : Top
*/
if(arr[nx][ny] == 1){
if(dir == 1)
return Node(nx,ny+1,0);
else if(dir == 2)
return Node(nx-1,ny,3);
else
return Node(nx,ny,changeDir[dir]);
}
111
000
000
-
위 처럼 있다면 (1,0)에서 시작하여 위로 가면 좌표를 바로 (0,2) 이동시키며 방향 또한 오른쪾으로 전환시킨다.
-
그러면 (0,2)에서 오른쪽으로 진행하는 경우로 인식하여 틀리게 되었다.
-
원래대로라면 (1,0) -> (0,0) -> (0,1) -> (0,0)으로 이동해야 하기 때문이다.
-
또다른 실수로는 웜홀에 빠져 다른 웜홀로 나오는 작업 부분에서 다음과 같이 코딩을 하였다.
if( m[ maze[x][y] ] == p(x,y) ){
x = m[ maze[x][y] * 2 ].first;
y = m[ maze[x][y] * 2 ].second;
}
-
이 때 내가 시작한 좌표가 (1,1)이라면 x와 y에는 각각 1이 들어가야한다.
-
하지만 위처럼 했을 경우에 x는 m[ maze[x][y] * 2 ].first 값에 따라 바뀌게 되고
그로인해 m[ maze[x][y] * 2 ].second 에서 x는 1이 아닌 이상한 값이 들어가게 된다. -
정상적으로 구현하기 위해선 다음과 같이 하면 된다.
int tmp_x;
int tmp_y;
if( m[ maze[x][y] ] == p(x,y) ){
tmp_x = m[ maze[x][y] * 2 ].first;
tmp_y = m[ maze[x][y] * 2 ].second;
}
else{
tmp_x = m[ maze[x][y] ].first;
tmp_y = m[ maze[x][y] ].second;
}
x = tmp_x;
y = tmp_y;