[백준oj] 1261번 알고스팟

www.acmicpc.net/problem/1261

1261번: 알고스팟

---

 

n과 m값이 작아서 bfs미로찾기로 해서, 해당 maze[i][j]마다 지나오며 부셨던 벽의 최소값을 저장해둔뒤, 도착지점의 최솟값을 출력하는 방식으로 짜보았다.

#include<iostream>
#include <algorithm>
#include<queue>
#define MAX 100*100+1
using namespace std;

int maze[100][100];
int result[100][100];
int check[100][100] = { 0 };
int N,M;
int mv[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

void bfs() {
	queue<pair<int, int>> q;

	q.push(make_pair(0,0));

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		check[x][y] = 1;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + mv[i][0];
			int ny = y + mv[i][1];

			if (nx >= 0 && nx < M&&ny >= 0 && ny < N) {
				if (check[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
                    //다음 발디딜 셀에 저장되어있는 최소값보다, 해당셀의 최소값+다음 셀의 벽유무
                    //값을 비교 후에 최소값 저장
					if (result[nx][ny] > result[x][y] + maze[nx][ny]) {
						result[nx][ny] = result[x][y] + maze[nx][ny];
					}
				}
			}
		}
	}
}

int main() {
	cin >> M>>N;
	char data;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> data;
			maze[i][j] = data - '0';
			result[i][j] = MAX;
		}
	}
	result[0][0] = 0;
	bfs();
	cout << result[N - 1][M - 1];
	return 0;
}

 

이렇게 했지만 결과는

내생각에는 n과 m의 값이 최대값인 100이됐을때 bfs를 돌며 쌓이는 큐의 메모리가 초과된다 생각했다.

 

 

 

그래서 다음으로 dfs로 풀어보았다.

#include<iostream>
#include <algorithm>
#include<utility>
#include<queue>
#define MAX 100*100+1
using namespace std;

int maze[100][100];
int result[100][100];
int check[100][100] = { 0 };
int N, M;
int mv[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

void dfs(int x,int y,int cnt) {
	if (result[x][y] <= cnt) return;//cnt가 더 크다면 이 길은 최솟값이 아니니 return
	else result[x][y] = cnt; //아니면 cnt저장 후 계속
   
   //도착하면 return
	if (x == N - 1 && y == M - 1) {
		return;
	}

	for (int i = 0; i < 4; i++) {
		int nx = x + mv[i][0];
		int ny = y + mv[i][1];
		//발디딜 수 있는 곳이라면
		if (nx >= 0 && nx < N&&ny >= 0 && ny < M&&check[nx][ny]==0) {
        	//dfs실행
			check[nx][ny] = 1;
			dfs(nx, ny, cnt + maze[nx][ny]);//벽의 개수는 지금까지 부신 벽+다음셀의 벽 유무
			check[nx][ny] = 0;
		}
	}
}

int main() {
	cin >> M >> N;
	char data;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> data;
			maze[i][j] = data - '0';
			result[i][j] = MAX;
		}
	}
	dfs(0,0,0);
	cout << result[N - 1][M - 1];
	return 0;
}

결과는 성공!