OJ 2206 : 벽 부수고 이동하기 - C++
벽 부수고 이동하기
코드
[ 시간초과 코드 ]
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
char board[1001][1001];
int cost[1001][1001];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0 , -1, 0};
int ans = 1e9;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M;
vector<pair<int,int>> v;
vector<pair<int,int>> real;
cin >> N >> M;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
{
cin >> board[i][j];
if(board[i][j] == '1')
v.push_back({i,j});
}
for(int i=0;i<v.size();i++)
{
auto cur = v[i];
int cnt=0;
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
if(board[ny][nx] != '1') cnt++;
}
if(cnt >= 2)
real.push_back(v[i]);
}
for(int i=0;i<real.size();i++)
{
board[real[i].first][real[i].second] = '0';
queue<pair<int,int>> q;
q.push({0,0});
cost[0][0] = 1;
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
if(board[ny][nx] == '1') continue;
if(cost[ny][nx] != 0 and (cost[ny][nx] < cost[cur.first][cur.second]+1)) continue;
q.push({ny, nx});
cost[ny][nx] = cost[cur.first][cur.second] + 1;
if(ny == N-1 and nx == M-1) goto stop;
}
}
stop:
if(cost[N-1][M-1] != 0)
ans = min(ans, cost[N-1][M-1]);
board[real[i].first][real[i].second] = '1';
}
if(ans == 1e9) cout << -1;
else cout << ans;
return 0;
}
- 로직
'1'
이 들어간 모든 좌표
에 대해 하나씩 값을 바꿔보며 BFS를 수행
해 최소값
을 찾기
- 실패 이유
: 시간초과
[ 정답 풀이 ]
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define INF 1e9
using namespace std;
char board[1001][1001];
int cost[2][1001][1001];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0 , -1, 0};
queue<pair<pair<int,int>,int>> q;
int ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
cin >> board[i][j];
for(int d=0;d<2;d++)
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
cost[d][i][j] = INF;
q.push({{0,0},0});
cost[0][0][0] = 1;
cost[1][0][0] = 1;
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first.first + dy[dir];
int nx = cur.first.second + dx[dir];
int status = cur.second;
if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
if(board[ny][nx] == '1'){
if(status == 0) status=1;
else continue;
}
if(cost[status][ny][nx] <= cost[cur.second][cur.first.first][cur.first.second]+1) continue;
q.push({{ny, nx}, status});
cost[status][ny][nx] = cost[cur.second][cur.first.first][cur.first.second] + 1;
if(ny == N-1 and nx == M-1) goto stop;
}
}
stop:
ans = min(cost[0][N-1][M-1], cost[1][N-1][M-1]);
if(ans == INF) cout << -1;
else cout << ans;
return 0;
}
- 핵심
board[N][M]
의 입장에서 각 칸은 벽을 부수고 온 경우
/ 벽을 부수지 않고 온 경우
로 2가지
가 존재
--> cost[2][N][M]
으로 각 상태에 따른 최단 경로
를 저장해야 함
queue
에 status
값도 함께 포함
(queue<pair<pair<int,int>,int>> q
)
Author And Source
이 문제에 관하여(OJ 2206 : 벽 부수고 이동하기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-2206-벽-부수고-이동하기-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
[ 시간초과 코드 ]
#include <iostream> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> using namespace std; char board[1001][1001]; int cost[1001][1001]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0 , -1, 0}; int ans = 1e9; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; vector<pair<int,int>> v; vector<pair<int,int>> real; cin >> N >> M; for(int i=0;i<N;i++) for(int j=0;j<M;j++) { cin >> board[i][j]; if(board[i][j] == '1') v.push_back({i,j}); } for(int i=0;i<v.size();i++) { auto cur = v[i]; int cnt=0; for(int dir=0;dir<4;dir++) { int ny = cur.first + dy[dir]; int nx = cur.second + dx[dir]; if(nx<0 or ny<0 or nx>=M or ny>=N) continue; if(board[ny][nx] != '1') cnt++; } if(cnt >= 2) real.push_back(v[i]); } for(int i=0;i<real.size();i++) { board[real[i].first][real[i].second] = '0'; queue<pair<int,int>> q; q.push({0,0}); cost[0][0] = 1; while(!q.empty()) { auto cur = q.front(); q.pop(); for(int dir=0;dir<4;dir++) { int ny = cur.first + dy[dir]; int nx = cur.second + dx[dir]; if(nx<0 or ny<0 or nx>=M or ny>=N) continue; if(board[ny][nx] == '1') continue; if(cost[ny][nx] != 0 and (cost[ny][nx] < cost[cur.first][cur.second]+1)) continue; q.push({ny, nx}); cost[ny][nx] = cost[cur.first][cur.second] + 1; if(ny == N-1 and nx == M-1) goto stop; } } stop: if(cost[N-1][M-1] != 0) ans = min(ans, cost[N-1][M-1]); board[real[i].first][real[i].second] = '1'; } if(ans == 1e9) cout << -1; else cout << ans; return 0; }
- 로직
'1'
이 들어간모든 좌표
에 대해 하나씩 값을 바꿔보며BFS를 수행
해최소값
을 찾기- 실패 이유
:시간초과
[ 정답 풀이 ]
#include <iostream> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #define INF 1e9 using namespace std; char board[1001][1001]; int cost[2][1001][1001]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0 , -1, 0}; queue<pair<pair<int,int>,int>> q; int ans; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M; for(int i=0;i<N;i++) for(int j=0;j<M;j++) cin >> board[i][j]; for(int d=0;d<2;d++) for(int i=0;i<N;i++) for(int j=0;j<M;j++) cost[d][i][j] = INF; q.push({{0,0},0}); cost[0][0][0] = 1; cost[1][0][0] = 1; while(!q.empty()) { auto cur = q.front(); q.pop(); for(int dir=0;dir<4;dir++) { int ny = cur.first.first + dy[dir]; int nx = cur.first.second + dx[dir]; int status = cur.second; if(nx<0 or ny<0 or nx>=M or ny>=N) continue; if(board[ny][nx] == '1'){ if(status == 0) status=1; else continue; } if(cost[status][ny][nx] <= cost[cur.second][cur.first.first][cur.first.second]+1) continue; q.push({{ny, nx}, status}); cost[status][ny][nx] = cost[cur.second][cur.first.first][cur.first.second] + 1; if(ny == N-1 and nx == M-1) goto stop; } } stop: ans = min(cost[0][N-1][M-1], cost[1][N-1][M-1]); if(ans == INF) cout << -1; else cout << ans; return 0; }
- 핵심
board[N][M]
의 입장에서 각 칸은벽을 부수고 온 경우
/벽을 부수지 않고 온 경우
로2가지
가 존재
-->cost[2][N][M]
으로 각 상태에 따른최단 경로
를 저장해야 함queue
에status
값도 함께 포함
(queue<pair<pair<int,int>,int>> q
)
Author And Source
이 문제에 관하여(OJ 2206 : 벽 부수고 이동하기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-2206-벽-부수고-이동하기-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)