바이준 1261 – 알고스팟
난이도: 골드 4
시간: 30분
질문
https://www.acmicpc.net/problem/1261
1261호: 알고스팟
첫 번째 행은 미로의 크기를 나타내는 가로 치수 M과 세로 치수 N(1≤N, M≤100)을 제공합니다. 다음 N 라인은 숫자 0과 1로 미로의 상태를 나타냅니다. 0은 빈 방을 의미하고 1은 벽을 의미합니다.
www.acmicpc.net
해결책
이 문제는 bfs를 사용하여 쉽게 해결할 수 있다고 생각합니다. 그래서 아무 생각 없이 코드를 작성했더니 메모리가 넘쳤다.
초기 코드
#include <iostream>
#include <queue>
#include <cstring>
using namespace::std;
int N, M;
int map(101)(101);
int v(101)(101);
int result = 999999999;
int ud(4) = {-1,1,0,0};
int lr(4) = {0,0,-1,1};
void bfs(int y, int x){
queue<pair<pair<int, int>, pair<int, int>>> q;
v(y)(x) = 1;
q.push({{y, x}, {0,0}});
while(!q.empty()){
int ny = q.front().first.first;
int nx = q.front().first.second;
int cnt = q.front().second.first;
q.pop();
if(ny == N && nx == M){
result > cnt ? result = cnt : 1;
continue;
}
v(ny)(nx) = 1;
for(int i=0; i<4; i++){
int ty = ny + ud(i);
int tx = nx + lr(i);
if(v(ty)(tx) == 0){
if(ty >= 1 && tx >= 1 && ty <= N && tx <= M){
if(map(ty)(tx) == 1){
q.push({{ty, tx}, {cnt+1, 0}});
}else{
q.push({{ty, tx}, {cnt, 0}});
}
}
}
}
}
}
int main(){
scanf("%d %d", &M, &N);
for(int i=1; i<=N; i++){
string tmp;
cin >> tmp;
for(int j=1; j<=M; j++){
map(i)(j) = tmp(j-1) - 48;
}
}
bfs(1,1);
printf("%d\n", result);
}
초기 코드의 문제
1. 벽을 최소화하는 경로는 나중에 일부 정점을 방문할 수 있습니다. 그러나 이미 많은 벽을 방문한 경로가 해당 정점을 방문하지 못하는 경우가 있습니다.
2. 대기열에 너무 많은 데이터가 있으면 메모리 오버플로가 발생합니다.
해결하다
1. 방문한 정점을 다시 방문할 수 있도록 벽이 부서진 횟수를 2D 배열에 저장합니다.
wall(i)(j) : 위치 (i,j)에 도달하기 위해 벽을 부수는 최소 횟수
그러므로, 꼭지점을 다시 방문하는 경우 이전에 저장된 벽 값을 현재 경로를 이동하는 동안 벽이 부서진 횟수와 비교하여 더 작은 값으로 업데이트합니다.하다.
이전 값 대신 새 값을 업데이트하면 해당 정점이 대기합니다..
2. 방법 1을 채택하면 모든 꼭짓점을 대기열에 넣지 않고 조건에 따라 넣기 때문에 메모리 오버플로 문제를 해결할 수 있습니다.
최종 코드
#include <iostream>
#include <queue>
#include <cstring>
#include <climits>
#define MAX 101
using namespace::std;
int N, M;
int map(MAX)(MAX);
int wall(MAX)(MAX);
int ud(4) = {-1,1,0,0};
int lr(4) = {0,0,-1,1};
void bfs(int y, int x){
queue<pair<int, int>> q;
q.push({y, x});
while(!q.empty()){
int ny = q.front().first;
int nx = q.front().second;
int cnt = wall(ny)(nx);
q.pop();
if(ny == N && nx == M){
continue;
}
for(int i=0; i<4; i++){
int ty = ny + ud(i);
int tx = nx + lr(i);
if(ty >= 1 && tx >= 1 && ty <= N && tx <= M){
if(map(ty)(tx) == 1){
if(wall(ty)(tx) > cnt+1){
wall(ty)(tx) = cnt+1;
q.push({ty, tx});
}
}else{
if(wall(ty)(tx) > cnt){
wall(ty)(tx) = cnt;
q.push({ty, tx});
}
}
}
}
}
}
int main(){
scanf("%d %d", &M, &N);
for(int i = 1; i<=N; i++){
for(int j = 1; j<=M; j++){
wall(i)(j) = INT_MAX;
}
}
for(int i=1; i<=N; i++){
string tmp;
cin >> tmp;
for(int j=1; j<=M; j++){
map(i)(j) = tmp(j-1) - 48;
}
}
wall(1)(1) = 0;
bfs(1,1);
printf("%d\n", wall(N)(M));
}
