백준 17484번 진우의 달 여행 (Small) C++ BFS, 너비 우선 탐색

리뷰

 

10달에 걸친 복수가 완료되었다. 아무것도 모르는 코린이 시절 날 괴롭혔던 문제

https://www.acmicpc.net/problem/17484

 

문제 풀이

1. n과 m값을 받아오고 n * m크기의 맵을 초기화 해준다.
2. 열의 개수 * 방향 배열의 개수 m * 3 만큼 for문을 개행시켜 주고, dfs의 매개변수로 열 인덱스와 방향 인덱스를 전달해 준다.
3. 0, col 부터 탐색을 시작하여 이전과 같은 방향은 가지 못하도록 탐색을 시작해 준다.
4. 현재 행이 n - 1에 도달한 경우 cv값을 ans와 비교해 최소값을 갱신해 준다.
5. 모든 탐색이 종료된 후 ans에 저장된 값을 출력해 주면 된다.

 

참고 사항

가지치기로 nv값이 이미 ans보다 크다면 큐에 추가해 줄 필요가 없다.

 

 

정답 코드

#include<iostream>
#include<queue>

using namespace std;

int dx[] = { 1, 1, 1 };
int dy[] = { -1, 0, 1 };
int lst[6][6];
int n, m, ans = 1e9;

struct Pos {
	int x, y, d, v;
};

void bfs(int col, int dir) {
	queue<Pos> q;
	q.push({ 0, col, dir, lst[0][col]});

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, cd = pos.d, cv = pos.v;
		if (cx == n - 1) {
			ans = min(ans, cv);
			continue;
		}
		for (int i = 0; i < 3; i++) {
			if (cd == i) continue;
			int nx = cx + dx[i], ny = cy + dy[i], nd = i;
			if (0 <= ny && ny < m) {
				int nv = cv + lst[nx][ny];
				if (nv < ans) q.push({ nx, ny, nd, nv });
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> lst[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < 3; j++) {
			bfs(i, j);
		}
	}
	cout << ans;
}