문제 : https://www.acmicpc.net/problem/2178
서론
https://hydroponicglass.tistory.com/14
과 같은 방식으로 이동횟수를 확인하고 방문하면 지도를 이동할 수 없는 0으로 갱신하는식으로 구현했는데,
시간초과가 발생했고 반복문의 종료조건에 반례가 있어서 무한루프가 발생됨을 확인.
수정하면 또다른 반례가 생길것 같아서 방문지 확인 배열을 만들었다.
이 방법이 깔끔하고 편한것 같다.
아이디어
입력이 라인단위로 되어있어서 라인을 숫자 하나씩 분할해야한다.
string 자료형으로 라인을 입력받으면 배열 한칸에 한 글자씩 들어가는데,
char로 된 배열 칸마다 int로 바꿔서 map에 넣으면 된다.
숫자 char를 int로 바꾸는 방법은 글자 '0'을 빼주면 된다.
그리고 BFS를 이용하여 풀이한다.
1. 시작좌표 0,0을 큐에 푸시하고 visit[0][0]를 1로 만든다.
2. 큐에서 하나를 빼낸다. 빼낸 좌표가 (y,x)면
2-1. 빼낸 좌표의 (y,x+1) map값이 1이고 방문하지 않았으면 visit[y][x+1] = visit[y][x]+1 하고 (y,x+1) 좌표를 큐에 푸시
2-2. 빼낸 좌표의 (y,x-1) map값이 1이고 방문하지 않았으면 visit[y][x-1] = visit[y][x]+1 하고 (y,x-1) 좌표를 큐에 푸시
2-3. 빼낸 좌표의 (y+1,x) map값이 1이고 방문하지 않았으면 visit[y+1][x] = visit[y][x]+1 하고 (y+1,x) 좌표를 큐에 푸시
2-4. 빼낸 좌표의 (y-1,x) map값이 1이고 방문하지 않았으면 visit[y-1][x] = visit[y][x]+1 하고 (y-1,x) 좌표를 큐에 푸시
좌표를 한칸씩 이동할때마다 방문값이 1 증가하여 최종 방문지(n,m)에서는 원하는 답인 최소 이동 값이 나온다.
최종 방문지를 한번 방문하면 다시 방문할 수 없기때문에 최소 이동값이 갱신되지 않는다.
3. 큐가 비어있지 않으면 2로 이동
4. visit의 n,m 좌표를 출력
구현
// c++
#pragma warning (disable : 4996)
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int map[101][101];
int visited[101][101];
int n, m;
char tmp[101];
void input() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
scanf("%s", &tmp);
for (int j = 0; j < m; j++) {
map[i][j] = tmp[j]-'0';
}
}
}
void bfs(int y, int x) {
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>>q;
int result = 0;
q.push(make_pair(y,x));
visited[y][x] = 1;
while (!q.empty()) {
result++;
y = q.front().first;
x = q.front().second;
q.pop();
for (int j = 0; j < 4; j++) {
int yy = y + dy[j];
int xx = x + dx[j];
if (yy >= 0 && xx >= 0 && yy < n && xx < m && map[yy][xx] == 1 && visited[yy][xx] == 0) {
q.push(make_pair(yy, xx));
visited[yy][xx] = visited[y][x] + 1;
}
}
}
}
int main() {
input();
bfs(0, 0);
cout << visited[n - 1][m - 1];
}
최근댓글