백준 1261번 알고스팟 C++, 파이썬

리뷰

C++, 파이썬 모두 힙을 사용한 BFS로 문제를 풀었다.

 

문제 풀이

1. m과 n을 입력받고 2차 배열을 입력 받는다, 방향 배열을 4방향으로 초기화 한 후 방문 배열도 n * m크기로 초기화 한다.
2. 힙에 (벽을 부순 횟수, x좌표, y좌표)를 초기화 해준다. 초기값은 (0, 0, 0)이다. 
3. 최소 벽을 출력할 min_wall 변수도 0으로 초기화 해주고 while 루프를 실행한다.
4. 현재 힙에 존재하는 벽이 가장 낮은 정보를 뽑아온다.
5. 만약 끝부분에 도달했다면 현재 까지 부순 벽의 수를 min_wall에 저장해 준다.
6. 그게 아니라면 4방향을 체크하며 범위 내에 존재하는지, 방문을 한적이 있는지를 체크해 준다.
7. 만약 방문을 하지 않은 좌표라면 방문 처리를 해주고, 해당 좌표의 값이 1이라면 부순 벽을 1만큼 올려준 뒤 해당 좌표를 힙에 추가해 준다.
8. 1이 아닐 경우 바로 힙에 좌표를 추가해 주면 된다.
9. while 루프가 종료된 후 min_wall 값을 출력해 준다.

 

참고 사항

입력 받는 2차배열이 공백으로 구분되어 있지 않은 점을 유의한다.

2차 배열의 값이 1이였을때 w 증가 및 힙에 추가 후 w를 다시 감소 시켜줘야 다음 for문에 영향이 없다.

 

정답 코드

C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int m, n;
vector<string> lst;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

struct pos {
	int wall, x, y;
};

struct cmp {
	bool operator()(pos left, pos right) {
		if (left.wall > right.wall) return true;
		if (left.wall < right.wall) return false;
		return false;
	}
};

int main() {
	cin >> m >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		lst.push_back(s);
	}
	priority_queue<pos, vector<pos>, cmp> q;
	vector<vector<int>> v(n, vector<int>(m, 0));
	q.push({ 0, 0, 0 });
	v[0][0] = 1;
	int min_wall = 0;
	while (!q.empty()) {
		pos cpos = q.top();
		q.pop();
		int cw = cpos.wall, cx = cpos.x, cy = cpos.y;
		if (cx == n - 1 && cy == m - 1) {
			min_wall = cw;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny]) {
				v[nx][ny] = 1;
				if (lst[nx][ny] == '1') {
					cw++;
					q.push({ cw, nx, ny });
					cw--;
				}
				else {
					q.push({ cw, nx, ny });
				}
			}
		}
	}
	cout << min_wall;
}

 

파이썬

import sys
import heapq

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
m, n = map(int, input().split())
lst = [list(input()) for _ in range(n)]
v = [[0] * m for _ in range(n)]
heap = [(0, 0, 0)]
v[0][0] = 1
min_wall = 0
while heap:
    w, x, y = heapq.heappop(heap)
    if x == n - 1 and y == m - 1:
        min_wall = w
        break
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and not v[nx][ny]:
            v[nx][ny] = 1
            if lst[nx][ny] == '1':
                w += 1
                heapq.heappush(heap, (w, nx, ny))
                w -= 1
            else:
                heapq.heappush(heap, (w, nx, ny))
print(min_wall)