백준 14948번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	골드 2

---

풀이

 벽부수고 넘어가기 문제와 저번 1939번 문제를 섞어둔듯한 문제이다. 1939번에서 사용한 그래프탐색+이분탐색과 벽부수기 풀이를 섞어서 시도했지만, 진짜 계속해서 틀렸고, 어디서 틀렸는지 감도 잡히지 않았다. 결국 다른 분의 풀이를 아주 조금 참조했다. visited 배열을 2차원이 아닌 3차원으로 처리하는 테크닉을 보고, 아 이런 테크닉이 있었지 하고 코드를 개선했다.

 

물론 개선했다고 읽기 좋은 코드라는건 아니다... 코드도 정리해야할거 같다.

WA코드

#include <bits/stdc++.h>
using namespace std;

int n, m, low, high;
vector<vector<int>> rokaf;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

void input() {
    cin >> n >> m;
    rokaf.resize(n, vector<int>(m));
    for(auto& row : rokaf) {
        for(int& lev : row) {
            cin >> lev;
            high = max(high, lev);
        }
    }
    low = rokaf[0][0];
}

bool bfs(int level) {
    queue<tuple<int,int,bool>> q;
    vector<vector<int>> visited(n, vector<int>(m, -1));

    visited[0][0] = 0;
    q.push({0, 0, false});

    while(!q.empty()) {
        auto [cur_row, cur_col, used] = q.front(); q.pop();

        if (cur_row == n - 1 && cur_col == m - 1) {
            return true;
        }

        for(int d = 0; d < 4; d++) {
            int nxt_row = cur_row + dy[d];
            int nxt_col = cur_col + dx[d];

            if (nxt_row < 0 || nxt_row >= n ||
                nxt_col < 0 || nxt_col >= m ||
                visited[nxt_row][nxt_col] == 0 ||
                (visited[nxt_row][nxt_col] == 1 && used) ||
                (rokaf[nxt_row][nxt_col] > level && used)) {
                continue;
            }

            if (rokaf[nxt_row][nxt_col] > level && !used) {
                int used_row = nxt_row + dy[d];
				int used_col = nxt_col + dx[d];

				if (used_row < 0 || used_row >= n ||
					used_col < 0 || used_col >= m ||
					rokaf[used_row][used_col] > level
					) {
					continue;
				}
				visited[nxt_row][nxt_col] = 1;
				visited[used_row][used_col] = 1;
				q.push({used_row, used_col, true});
            }
            else {
                visited[nxt_row][nxt_col] = used;
                q.push({nxt_row, nxt_col, used});
            }
        }
    }

    return false;
}

void sol() {
    int mid;
    while(low <= high) {
        mid = (low + high) / 2;
        if (bfs(mid)) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    cout << low;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    input();
    sol();
}

AC 코드

#include <bits/stdc++.h>
using namespace std;

int n, m, low, high;
vector<vector<int>> rokaf;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

void input() {
	cin >> n >> m;
	rokaf.resize(n, vector<int>(m));
	for(auto& row : rokaf) {
		for(int& lev : row) {
			cin >> lev;
			high = max(high, lev);
		}
	}
	low = rokaf[0][0];
}

bool bfs(int level) {
	queue<tuple<int,int,bool>> q;
	bool visited[n][m][2]{};

	visited[0][0][0] = true;
	q.push({0, 0, false});

	while(!q.empty()) {
		auto [cur_row, cur_col, used] = q.front(); q.pop();

		if (cur_row == n - 1 && cur_col == m - 1) {
			return true;
		}

		for(int d = 0; d < 4; d++) {
			int nxt_row = cur_row + dy[d];
			int nxt_col = cur_col + dx[d];

			if (nxt_row < 0 || nxt_row >= n ||
				nxt_col < 0 || nxt_col >= m ||
				visited[nxt_row][nxt_col][used] ||
				rokaf[nxt_row][nxt_col] > level) {
				continue;
			}
			visited[nxt_row][nxt_col][used] = true;
			q.push({nxt_row, nxt_col, used});
		}

		for(int d = 0; !used && d < 4; d++) {
			int nxt_row = cur_row + dy[d];
			int nxt_col = cur_col + dx[d];

			if (nxt_row < 0 || nxt_row >= n ||
				nxt_col < 0 || nxt_col >= m ||
				rokaf[nxt_row][nxt_col] <= level) {
				continue;
			}

			nxt_row += dy[d], nxt_col += dx[d];

			if (nxt_row < 0 || nxt_row >= n ||
				nxt_col < 0 || nxt_col >= m ||
				visited[nxt_row][nxt_col][1] ||
				rokaf[nxt_row][nxt_col] > level) {
				continue;
			}

			visited[nxt_row][nxt_col][1] = true;
			q.push({nxt_row, nxt_col, true});
		}
	}

	return false;
}

void sol() {
	int mid;
	while(low <= high) {
		mid = (low + high) / 2;
		if (bfs(mid)) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	cout << low;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}

 

설날부터 2월까진 여행일정이 많아 이 기간동안은 블로그 문제 정리가 뜸해질 예정이다.