#include <cstdio> #include <vector> #include <algorithm> #include <queue> #include <cstring> using namespace std; struct pt { int x; int y; int d; pt(int a, int b, int c) :x(a), y(b), d(c) {} }; int n; char board[53][53]; int visited[52][52][2]; int dist[52][52][2]; vector<pt> avail(const pt& cur) { vector<pt> ret; int dd[4][2] = { { -1,0 },{ 0,1 },{ 1,0 },{ 0,-1 } }; bool res[4] = { 0 }; bool range = true; for (int i = 0; i<4; ++i) { range = true; for (int j = -1; j <= 1; ++j) { int rx = (cur.d ? cur.x + j : cur.x) + dd[i][0]; int ry = (cur.d ? cur.y : cur.y + j) + dd[i][1]; if (rx<1 || rx>n || ry<1 || ry>n || board[rx][ry] == '1') { range = false; break; } } if (!range)continue; ret.push_back(pt(cur.x + dd[i][0], cur.y + dd[i][1], cur.d)); } int dx[] = { -1,-1,-1,0,1,1,1,0 }; int dy[] = { -1,0,1,1,1,0,-1,-1 }; bool turn = true; for (int i = 0; i<8; ++i) { int x = cur.x + dx[i]; int y = cur.y + dy[i]; if (x<1 || x>n || y<1 || y>n || board[x][y] == '1') { turn = false; break; } } if (turn)ret.push_back(pt(cur.x, cur.y, cur.d ^ 1)); return ret; } int bfs() { memset(visited, 0, sizeof(visited)); memset(dist, 0, sizeof(dist)); int startX = -1; int startY = -1; int startDirection = -1; //0 가로 1세로 int endX = -1; int endY = -1; int endDirection = -1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (j + 2 <= n && board[i][j] == 'B' && board[i][j + 1] == 'B' && board[i][j + 2] == 'B') { startX = i; startY = j + 1; startDirection = 0; break; } if ((i + 2 <= n) && (board[i][j] == 'B') && (board[i + 1][j] == 'B') && (board[i + 2][j] == 'B')) { startX = i + 1; startY = j; startDirection = 1; break; } } if (startDirection != -1)break; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (j + 2 <= n && board[i][j] == 'E' && board[i][j + 1] == 'E' && board[i][j + 2] == 'E') { endX = i; endY = j + 1; endDirection = 0; break; } if (i + 2 <= n && board[i][j] == 'E' && board[i + 1][j] == 'E' && board[i + 2][j] == 'E') { endX = i + 1; endY = j; endDirection = 1; break; } } if (endDirection != -1)break; } visited[startX][startY][startDirection] = 1; queue<pt> q; q.push(pt(startX, startY, startDirection)); while (!q.empty()) { pt cur = q.front(); q.pop(); int distance = dist[cur.x][cur.y][cur.d]; vector<pt> adj = avail(cur); int sz = (int)adj.size(); for (int i = 0; i<sz; ++i) { pt next = adj[i]; if (!visited[next.x][next.y][next.d]) { q.push(next); visited[next.x][next.y][next.d] = 1; dist[next.x][next.y][next.d] = distance + 1; } } } return dist[endX][endY][endDirection]; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i)scanf("%s", board[i] + 1); printf("%d",bfs()); } |
저장해두고, 방문한 것 체크할때, 가운데 숫자를 저장하고, 그리고 거리도 저장하고, 오께이, 3차원을 저장한 것은 가로 세로에 대한 것이 있기 때문입니다. 갈수 있는지 없는지를 체크하면 됩니다. 아하 갈 수 있는 것들을 모두 체크해서 큐에 저장한 것에서 하나씩 가는 것입니다. 이정도 난이도 충분히 나올 수 있을 것 같습니다. 여기서 저는 bfs 가 아닌 dfs 로 풀이하다가 틀렸고, 방향과 중심점을 사용한 저장 방법에 대해서 알지 못했습니다. 여기서 board 로 처음에 입력을 받고 나서, 방문점을 저장하는 배열과 거리르 저장하는 배열이 있습니다. 이것을 활용하도록 합니다. 최소 몇 회 인가 이런게 없으면 dfs 가 아닌 bfs 로 풀이하는 쪽으로 생각해보도록 하겠습니다. |