Velog Posting #2206 벽 부수고 이동하기
#1442 벽부수고 이동하기 2
벽 부수고 이동하기 첫 번째 문제와 다른 점은 첫 번째는 최대 1개까지 벽을 부술 수 있었지만 이번엔 K개까지 부술 수 있었다. 그래서
bool discovered[MAX][MAX][2]
에서
bool discovered[MAX][MAX][10]
로 바꾸고 (K의 Max가 10이기 때문에)
다음 위치가 벽이고 현재까지 부순 벽의 수가 K개 미만 일 때 벽을 한 개 부수고 다음 지점을 방문한다
if (map[nx_y][nx_x] == PATH && !discovered[nx_y][nx_x][brk]) { discovered[nx_y][nx_x][brk] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt+1))); } else if (map[nx_y][nx_x] == WALL && brk < K) { discovered[nx_y][nx_x][brk+1] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk+1, cnt + 1))); }
그런데 이렇게 하니 계속 시간 초과가 떠서 다른 사람의 코드를 참조했다
if (!discovered[nx_y][nx_x][brk]) { if (map[nx_y][nx_x] == PATH) { discovered[nx_y][nx_x][brk] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt + 1))); } else if (map[nx_y][nx_x] == WALL && brk < K) { discovered[nx_y][nx_x][brk + 1] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk + 1, cnt + 1))); } }
먼저 다음 위치가 한 번도 방문 되지 않았을 때를 전제로 하고 약간 수정한 건데 어디서 그렇게 시간 차이가 나는 건지 모르겠다 ㅠㅠ cin, cout 에서 시간 초과가 난건지도..
전체 코드
#include <iostream> #include <vector> #include <queue> #include <string.h> using namespace std; const int MAX = 1001; const int PATH = 0; const int WALL = 1; int N, M,K; int dy[4] = { 0,0,1,-1 }; int dx[4] = { 1,-1,0,0 }; bool discovered[MAX][MAX][10]; vector<vector<int>> map; void input() { memset(discovered, false, sizeof(discovered)); cin >> N >> M >> K; map = vector<vector<int>>(N, vector<int > (M)); for (int i = 0; i < N; i++) { string tmp; cin >> tmp; for (int j = 0; j < M; j++) { int num = tmp[j] - '0'; map[i][j]=num; } } } int dfs() { queue <pair<pair<int, int>, pair<int, int>>> q; q.push(make_pair(make_pair(0, 0), make_pair(0, 1))); discovered[0][0][0] = true; while (!q.empty()) { int y = q.front().first.first; int x = q.front().first.second; int brk = q.front().second.first; int cnt = q.front().second.second; q.pop(); if (y == N - 1 && x == M - 1) return cnt; for (int i = 0; i < 4; i++) { int nx_y = y + dy[i]; int nx_x = x + dx[i]; if (nx_y < 0 || nx_x < 0 || nx_y >= N || nx_x >= M) continue; if (!discovered[nx_y][nx_x][brk]) { if (map[nx_y][nx_x] == PATH) { discovered[nx_y][nx_x][brk] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt + 1))); } else if (map[nx_y][nx_x] == WALL && brk < K) { discovered[nx_y][nx_x][brk + 1] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk + 1, cnt + 1))); } } //if (map[nx_y][nx_x] == PATH && !discovered[nx_y][nx_x][brk]) { // discovered[nx_y][nx_x][brk] = true; // q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt+1))); //} //else if (map[nx_y][nx_x] == WALL && brk < K) { // discovered[nx_y][nx_x][brk+1] = true; // q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk+1, cnt + 1))); //} } } return -1; } int main() { input(); printf("%d\n", dfs()); return 0; }