<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)

### 전체탐색 ###

### SRM 433.5 Div2 Level 2 ###

<소스코드>

#include <vector>
#include <queue>
#include <string>
using namespace std;
 
int rSize, cSize;
int visited[51][51];
 
struct P { 
    int r, c; 
    P(int r, int c) : r(r), c(c) {}
};
 
bool safe(int r, int c)
{
    return (0 <= r && r < rSize) && (0 <= c && c < cSize);
}
 
class MazeMaker {
public:
    int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
        rSize = maze.size();
        cSize = maze[0].size();
               
        P cur(startRow, startCol);
        visited[startRow][startCol] = 1;
        
        queue<P> q;
        q.push(cur);
 
        while(!q.empty()) {
            int curR = q.front().r;
            int curC = q.front().c; q.pop();
 
            int sz = moveRow.size();
            for(int k=0; k<sz; k++) {
                int nr = curR + moveRow[k];
                int nc = curC + moveCol[k];
                if(safe(nr, nc) && maze[nr][nc] == '.' && !visited[nr][nc]) {
                    P tmp(nr, nc);
                    q.push(tmp);
                    visited[nr][nc] = visited[curR][curC]+1;
                }
            }
        }
        int ans = 0;
        for(int r=0; r<rSize; r++) {
            for(int c=0; c<cSize; c++) {
                if(maze[r][c] == '.' && visited[r][c] == 0) return -1;
                if(maze[r][c] == '.' && ans < visited[r][c]) {
                    ans = visited[r][c];
                }
            }
        }
        return ans-1;
    }
};
 

>> 방문할 수 있는 모든 곳을 탐색. 방문을 못한 곳이 있으면 -1; 모두 방문했다면, 방문한 곳중 가장 먼 곳이 정답.