8주차 스터디 그래프 이론 - 백준 1261번 알고스팟

www.acmicpc.net/problem/1261

1261번: 알고스팟

IDEA

좌측 상단에서 우측 하단 까지 가는데 벽을 최소 몇 개 부숴야 하는 지 묻는 문제다. 

여러가지 방법으로 풀 수 있겠지만, 이 또한 다익스트라 로 풀었다. 풀고보니 bfs 같은 느낌도 있다,,,

좌측 상단 = 시작 지점 

부숴야 하는 벽의 개수 = 비용 으로 바라보면 시작지점부터 어떤 한 정점(우측 하단) 까지의 최소비용을 묻는 문제로 바꿔 생각할 수 있다.

 

음,,, 다익스트라 예제를 검색하면 보통 단순히 1753번 같은그래프 예제밖에 나오지 않는다.그래서 2차원좌표에 대해 다익스트라,,,? 라고 살짝 겁먹었지만 그냥 상하좌우를 확인해주는 코드만 넣어주면 된다!

 

최소 힙 큐에는 x,y 좌표와 0,0좌표부터 x,y좌표까지 오는 데 부순 벽의 개수를 저장해준다. 힙 큐에서 pop한 좌표인 x,y의 상하좌우를 살펴봐준다. 상하좌우가 범위를 벗어나지 않고 아직 방문되지 않았다면 그 좌표에 벽이 있는 지, 없는 지에 따라 달라진다.

 

새로운 좌표 (x,y의 상하좌우 중 하나)가 0이라면 그 이전 좌표에서 새로운 좌표까지 오는데 벽을 부수지 않아도 되는 것이므로,  이전 좌표의 cost 값과 새로운 좌표의 cost 값은 같아질 것이다. 원래 새로운 좌표의 cost값과 이전 좌표의 cost값 중 더 작은 것을 선택한다.

 

새로운 좌표 (x,y의 상하좌우 중 하나)가 1이라면 이전 좌표에서 새로운 좌표까지 오는데 벽을 부숴야 하므로, 부숴야 하는 벽의 개수가 1만큼 커져야한다. 새로운 좌표의 cost는 이전 좌표의 cost + 1 (새로운 좌표의 벽 부숴야 진입가능)이다. 원래 새로운 좌표의 cost값과 이전 좌표의 cost + 1 중 더 작은 값을 선택해주면 된다.

 

여기서 visited를 안해주면 큐에 계속 들어가게 돼서 visited처리를 꼭 해줘야한다. visited 처리를 해주면 나중에 들렸을 때, 최소일 수도 있지 않나? 라고 생각할 수도 있다. 우선순위 큐로 구현한 "다익스트라" 자체가 시작지점부터 cost가 제일 작은 정점부터 탐색하므로 만약 나중에 들렸다면 이미 제일 작은 cost 값이 저장되어있을 거기 때문에, 바로 visited처리를 해줘도 된다.   

 

CODE - C ++

#include <iostream>
#include <vector>
#include<algorithm>
#include<queue>
#include<string.h>

using namespace std;

int map[105][105] = { 0 };
int cost[105][105] = { 0 };
bool visited[105][105] = { false };
queue<pair<int, int>> q;
int n, m;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void find_path() {
	q.push({ 1,1 });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		visited[x][y] = true;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 < nx && nx <= m && 0 < ny && ny <= n &&!visited[nx][ny]) {
				if (map[nx][ny] == 0) cost[nx][ny] = min(cost[x][y] , cost[nx][ny]);
				else cost[nx][ny] = min(cost[nx][ny], cost[x][y] + 1);
				q.push({ nx,ny });
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) scanf("%1d", &map[i][j]);
	}
	memset(cost, 10000, sizeof(cost));
	cost[1][1] = 0;
	find_path();
	printf("%d", cost[m][n]);
}

 

CODE - Python 

import sys
input = sys.stdin.readline

from heapq import heappush , heappop


dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

n,m = map(int, input().split())

miro = [ list(map(int,input().strip())) for _ in range(m)]
cost = [[987654321 for _ in range(n)] for _ in range(m)]
visited = [[False for _ in range(n) ] for _ in range(m)]

def check (x,y):
  return 0 <= x < m and 0 <= y < n and not visited[x][y]

def dijkstra():
  heap = []
  heappush(heap,[0,0,0]) # cost ,노드
  cost[0][0] = 0
  visited[0][0] = True

  while heap:
    cur_cost , x, y = heappop(heap)
    for i in range(4) : 
      nx = x + dx[i]
      ny = y + dy[i]
      if check(nx,ny):
        if miro[nx][ny]: 
          cost[nx][ny] = min(cost[nx][ny] , cost[x][y] + 1)
        else :
          cost[nx][ny] = min(cost[nx][ny] , cost[x][y])
        heappush(heap ,[cost[nx][ny] , nx, ny])
        visited[nx][ny] = True

  print(cost[m-1][n-1])

dijkstra()