1. bfs() 가장 기본 문제 입니다. 2. STL을 사용도 해보고,queArr 를 사용도 해봤습니다. queArr 사용시 주의할 점은 rear, front 의 설정입니다. 그리고 사이즈 처음에 넣어주는 것도 확인해야 합니다. 그리고 각각 큐 stl 에 들어가는 부분을 변경해주면 됩니다. 간단합니다. 간단하면서 디버깅하기에 용의합니다. |
/* 2018.04.01 11:01 시작 1226 미로1 아냐, 일단 그냥 큐로 사용하도록 하겠습니다. 큐가 간편합니다. 그리고 bfs 로 역추적이나, 그 안의 값을 알아야 한다면 그때 배열을 사용하도록 하겠습니다. */ #include <iostream> #include <queue> #include <algorithm> #include <string> #include <memory.h> using namespace std; #define SIZE 16 int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int x, y, nx, ny; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int ans; int startX, startY, endX, endY; struct point { int x, y; }queArr[SIZE*SIZE]; queue<point> que; string str; int rear, front; void problemIn() { for (int i = 0; i < SIZE; i++) { cin >> str; for (int j = 0; j < SIZE; j++) { map[i][j] = str[j] - '0'; if (map[i][j] == 2) { startX = i; startY = j; } if (map[i][j] == 3) { map[i][j] = 0; endX = i; endY = j; } } } } void init() { for (int i = 0; i < 16; i++) { for (int j = 0; j < 16; j++) { visit[i][j] = 0; } } memset(queArr, 0, sizeof(queArr)); // queue<point> empty; // swap(que, empty); ans = 0; } void bfs() { while (rear != front) {
front++; x = queArr[front].x; y = queArr[front].y; if (x == endX && y == endY) { ans = 1; return; } for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= 16 || ny >= 16) continue; if (visit[nx][ny] == 0 && map[nx][ny] == 0) { visit[nx][ny] = 1; rear++; queArr[rear].x = nx; queArr[rear].y = ny; } } } } void solve() {
rear = front = -1; rear++; queArr[rear].x = startX; queArr[rear].y = startY; visit[startX][startY] = 1; bfs(); } int main() { for (int i = 0; i < 10; i++) { int tc; cin >> tc; problemIn(); solve(); cout << "#" << tc << " " << ans << endl; init(); } return 0; } |