🔗 문제
https://www.acmicpc.net/problem/1938
✏️ 풀이
문제에 나와 있는 배열을 보면 뭔가 막막한 감정이 들게 한다..
하지만 쫄지 않으면 무조건 풀 수 있다!
문제를 읽으며 "가중치가 없는 최단 경로"구하기라는 것을 알았고 BFS로 알고리즘을 특정했다.
BFS의 재방문 방지를 위한 유니크한 값이 필요하다.
그래서 통나무가 차지하는 3칸 중 하나의 위치를 기준으로 잡아주었다.
나는 중간에 있는 위치를 기준으로 잡았다.
회전을 할 때 중심을 기준으로 8방 탐색을 하면 쉽기 떄문이다!
그리고 재방문체크는 3차원 배열을 이용해준다.
bool visited[가로니?][x][y]같은 좌표라고 하더라도 통나무의 방향이 (가로)인지 (세로)인지에 따라서 갈 수 있는 방향이 달라지기 때문에 구별이 필요하다.
🙊 리팩토링 전 코드 (함수와 반복문의 소중함을 알아보자!)
거의 뭐 어디 한 번 해보자는 식의 노가다식 코드
일단 풀어야 하니까!!!! 제한된 시간 내에 할 수 있는 것에 최선을 다 했을 뿐입니다…
#include <iostream>
#include <vector>
#include <queue>
#define MAX 51
#define DIR_SIZE 9
typedef std::pair<int, int> pii;
const int dx[DIR_SIZE] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy[DIR_SIZE] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
int N;
bool grid[MAX][MAX] = {false, };
bool isValid(const int x, const int y)
{
return !(x < 0 || y < 0 || x >= N || y >= N || grid[x][y]);
}
std::vector<pii> start, end;
struct Node
{
Node() = default;
Node(int d, int x, int y) : d(d), x(x), y(y) {}
int d, x, y;
};
bool isDone(const Node& target, const Node& dest)
{
return (dest.d == target.d
&& dest.x == target.x
&& dest.y == target.y);
}
int bfs()
{
int answer = 0;
Node dest = {(end[0].first == end[1].first), end[1].first, end[1].second};
std::queue<Node> q; // 통나무의 가로 세로 여부와 통나무 중앙 위치를 중심으로 저장
q.push({(start[0].first == start[1].first), start[1].first, start[1].second});
bool visited[2][MAX][MAX] = {false, };
visited[q.front().d][q.front().x][q.front().y] = true;
while(!q.empty())
{
int qSize = q.size();
while(qSize--)
{
const int d = q.front().d;
const int x = q.front().x;
const int y = q.front().y;
if(isDone(q.front(), dest))
return answer;
q.pop();
if (!d) // 통나무가 세워져있음
{
//U
if (isValid(x-1, y) && isValid(x-2, y)
&& !visited[d][x-1][y])
{
visited[d][x-1][y] = true;
q.push({d, x-1, y});
}
//D
if (isValid(x+1, y) && isValid(x+2, y)
&& !visited[d][x+1][y])
{
visited[d][x+1][y] = true;
q.push({d, x+1, y});
}
//L
if (isValid(x, y-1) && isValid(x-1, y-1) && isValid(x+1, y-1)
&& !visited[d][x][y-1])
{
visited[d][x][y-1] = true;
q.push({d, x, y-1});
}
//R
if (isValid(x, y+1) && isValid(x-1, y+1) && isValid(x+1, y+1)
&& !visited[d][x][y+1])
{
visited[d][x][y+1] = true;
q.push({d, x, y+1});
}
//T
if(!visited[!d][x][y])
{
bool flag = true;
for (int i = 0; i < DIR_SIZE; ++i)
{
if (!isValid(x + dx[i], y + dy[i])) {
flag = false;
break;
}
}
if (flag) {
visited[!d][x][y] = true;
q.push({!d, x, y});
}
}
}
else // 통나무가 누워져있음
{
//U
if (isValid(x-1, y-1) && isValid(x-1, y) && isValid(x-1, y+1)
&& !visited[d][x-1][y])
{
visited[d][x-1][y] = true;
q.push({d, x-1, y});
}
//D
if (isValid(x+1, y-1) && isValid(x+1, y) && isValid(x+1, y+1)
&& !visited[d][x+1][y])
{
visited[d][x+1][y] = true;
q.push({d, x+1, y});
}
//L
if (isValid(x, y-1) && isValid(x, y-2)
&& !visited[d][x][y-1])
{
visited[d][x][y-1] = true;
q.push({d, x, y-1});
}
//R
if (isValid(x, y+1) && isValid(x, y+2)
&& !visited[d][x][y+1])
{
visited[d][x][y+1] = true;
q.push({d, x, y+1});
}
//T
if(!visited[!d][x][y])
{
bool flag = true;
for (int i = 0; i < DIR_SIZE; ++i)
{
if (!isValid(x + dx[i], y + dy[i])) {
flag = false;
break;
}
}
if (flag) {
visited[!d][x][y] = true;
q.push({!d, x, y});
}
}
}
}
++answer;
}
return 0;
}
int main()
{
std::cin >> N;
char ch;
for(int i=0; i<N; ++i)
{
for(int j=0; j<N; ++j)
{
std::cin >> ch;
grid[i][j] = (ch=='1');
if(ch == 'B')
start.push_back({i, j});
else if(ch=='E')
end.push_back({i, j});
}
}
std::cout << bfs();
return 0;
}
#반복문
사방으로 움직이는 것은 반복문으로 대체할 수 있다.
회전할 방향을 담은 dx, dy를 선언한 후에 적절히 사용해주자.
#회전
회전하는 부분은 가로와 세로의 구분 없이 모두 8방탐색을 하므로 중복되는 코드를 제거할 수 있다.
#재활용
4방탐색이나 8방탐색이나 굳이 따로 방향 배열을 만들 필요 없이 재활용할 수 있는건 하자!
💾 소스
♻️ 리팩토링 후
#include <iostream>
#include <vector>
#include <queue>
#define MAX 51
#define DIR_SIZE 9
typedef std::pair<int, int> pii;
const int dx[DIR_SIZE] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy[DIR_SIZE] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
int N;
bool grid[MAX][MAX] = {false, };
bool isValid(const int x, const int y)
{
return !(x < 0 || y < 0 || x >= N || y >= N || grid[x][y]);
}
std::vector<pii> start, end;
struct Node
{
Node() = default;
Node(int d, int x, int y) : d(d), x(x), y(y) {}
int d, x, y;
};
bool isDone(const Node& target, const Node& dest)
{
return (dest.d == target.d
&& dest.x == target.x
&& dest.y == target.y);
}
int bfs()
{
int answer = 0;
Node dest = {(end[0].first == end[1].first), end[1].first, end[1].second};
std::queue<Node> q; // 통나무의 가로 세로 여부와 통나무 중앙 위치를 중심으로 저장
q.push({(start[0].first == start[1].first), start[1].first, start[1].second});
bool visited[2][MAX][MAX] = {false, };
visited[q.front().d][q.front().x][q.front().y] = true;
while(!q.empty())
{
int qSize = q.size();
++answer;
while(qSize--)
{
int mx = q.front().x; int my = q.front().y;
int isHorizontal = q.front().d;
q.pop();
int fx = (isHorizontal ? mx : mx-1 );
int fy = (isHorizontal ? my-1 : my);
int lx = (isHorizontal ? mx : mx+1 );
int ly = (isHorizontal ? my+1 : my);
for(int d=1; d<DIR_SIZE; d+=2)
{
int x = mx + dx[d];
int y = my + dy[d];
if(!isValid(x, y) || visited[isHorizontal][x][y]
|| !isValid(fx + dx[d], fy + dy[d])
|| !isValid(lx + dx[d], ly + dy[d]))
continue;
if(isDone({isHorizontal, x, y}, dest))
return answer;
visited[isHorizontal][x][y] = true;
q.push({isHorizontal, x, y});
}
// TURN
if(visited[!isHorizontal][mx][my]) continue;
bool flag = true;
for (int d=0; d<DIR_SIZE; ++d)
{
if (!isValid(mx + dx[d], my + dy[d]))
{
flag = false;
break;
}
}
if (flag)
{
visited[!isHorizontal][mx][my] = true;
q.push({!isHorizontal, mx, my});
}
}
++answer;
}
return 0;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> N;
char ch;
for(int i=0; i<N; ++i)
{
for(int j=0; j<N; ++j)
{
std::cin >> ch;
grid[i][j] = (ch=='1');
if(ch == 'B')
start.push_back({i, j});
else if(ch=='E')
end.push_back({i, j});
}
}
std::cout << bfs();
return 0;
}