117. 탈출

백준

1. Python

from collections import deque

#이동할 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
  #큐 구현을 위해 deque 라이브러리 사용
  queue.append((x,y))
  c[x][y] = 1
  #큐가 빌 때까지 반복
  while queue:
    qlen = len(queue)
    while qlen:
      x, y = queue.popleft()
      #현재 위치에서 네 방향으로의 위치 확인
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        #공간을 벗어나지 않을 때만
        if 0 <= nx < n and 0 <= ny < m:
          #'.'이고 처음 방문하는 경우에만 최단 거리 기록
          if graph[nx][ny] == '.' and c[nx][ny] == 0:
            c[nx][ny] = c[x][y] + 1
            queue.append((nx, ny))
          elif graph[nx][ny] == 'D':
            print(c[x][y])
            return
      qlen -= 1
    water()
  print("KAKTUS")
  return

#물 이동
def water():
    qlen = len(wqueue)
    while qlen:
        x, y = wqueue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == '.':
                    graph[nx][ny] = '*'
                    wqueue.append((nx, ny))
        qlen -= 1


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

'''타임에러
#2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
  graph.append(list(map(str, input())))
'''

graph = [list(map(str, input())) for _ in range(n)]

c = [[0]*m for _ in range(n)]

queue, wqueue = deque(), deque()

for i in range(n):
    for j in range(m):
        if graph[i][j] == 'S':
            x1, y1 = i, j
            graph[i][j] = '.'
        elif graph[i][j] == '*':
            wqueue.append((i, j))

water() #물 먼저 채우기
bfs(x1, y1)

• 앞으로 물이 찰 곳을 못간다는 것은 물을 먼저 채우는 것으로 해결할 수 있다.

2. C++ - 공간복잡도 에러

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int, int> pii;     // 좌표를 담을 예정임  
int r, c;
char forest[50][51];

pii ddg;
vector<pii> water;
pii biber;
queue<pii> water_q, ddg_q;  // 좌표를 저장하는 queue
int ans;
// 방문 배열.... 
int water_vt[50][50] = {0, }, ddg_vt[50][50] = {0, };
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}; // 4방향 위치 값 

bool check_rc(int param_r, int param_c) {
    return 0 <= param_r && param_r < r && 0 <= param_c && param_c < c;
}

int main() {
    //freopen("res/B3055.in", "r", stdin);
    // 입력 받는 부분
    // 각자 자신만의 방법으로 
    scanf("%d%d", &r, &c);
    //cin >> r >> c;
    for (int i = 0 ; i < r ; i++) {
        scanf("%s", forest[i]);
    }

    // 할일
    // 두더지의 시작점이 어디인지 확인
    // 물 들은 어디에 있는지 확인
    // 비버의  굴
    for (int i = 0 ; i < r ; i++) {
        for (int j = 0 ; j < c ; j++) {
            if (forest[i][j] == 'S') {
                ddg = pii(i, j);
                // 어짜피 S는 하나일테니까. 필요하면 중단하는것을 넣어도 됨 
            }
            if (forest[i][j] == '*') {
                water.push_back(pii(i, j));
            }
            if (forest[i][j] == 'D') {
                biber = pii(i, j);
            }
        }
    }

    // 물 
    for (int i = 0 ; i < water.size() ; i++) {
        pii cur_water = water[i];
        water_q.push(cur_water);
        water_vt[cur_water.first][cur_water.second] = 1;
    }

    // 두더 지  
    ddg_q.push(ddg);
    ddg_vt[ddg.first][ddg.second] = 1;

    // 물과 두더지를 탐색하면서 갈수 있는지 없는지 판단
    // 두더지가 비버의 굴을 탐색하면 거리를 출력하고 끝 
    // 두더지가 더이상 탐색을 못하면 KAKTUS를  출력하고 끝  
    while (!ddg_q.empty()) {
        // 물 이동
        // q에서 하나를 꺼내고 상/하/좌/우로 이동
        // 비버의 목적지는 가지말고
        // 돌멩이도 가지 말고
        // 두더지??? 가도됨 
        int water_qsz = water_q.size();
        for (int i = 0 ; i < water_qsz ; i++) { // 현재에 q에 있었던 만큼만 탐색을 할꺼다... 
            pii cur_water = water_q.front();
            water_q.pop();
            for (int j = 0 ; j < 4 ; j++) { // 상/하/좌/우 순서대로 좌표를 얻는다  
                int new_r, new_c;
                new_r = cur_water.first + dr[j];
                new_c = cur_water.second + dc[j];
                if (!check_rc(new_r, new_c)) continue;
                if (forest[new_r][new_c] == 'D' || forest[new_r][new_c] == 'X' || water_vt[new_r][new_c] != 0) continue;
                water_vt[new_r][new_c] = water_vt[cur_water.first][cur_water.second] + 1;
                water_q.push(pii(new_r, new_c));
            }
        }

        // 두더지 이동 
        // queue에서 하나를 꺼내고 상/하/좌/우로 이동 
        // 물은 가지 말고 
        // 돌멩이도 가지말고
        // 목적지였으면?? 찾은것 
        int ddg_qsz = ddg_q.size();
        for (int i = 0 ; i < ddg_qsz ; i++) {
            pii cur_ddg = ddg_q.front();
            ddg_q.pop();
            for (int j = 0 ; j < 4 ; j++) {
                int new_r, new_c;
                new_r = cur_ddg.first + dr[j];
                new_c = cur_ddg.second + dc[j];
                if (!check_rc(new_r, new_c)) continue;
                if (forest[new_r][new_c] == 'X' || water_vt[new_r][new_c] != 0) continue;

                if (forest[new_r][new_c] == 'D') {
                    // 찾았다  
                    ans = ddg_vt[cur_ddg.first][cur_ddg.second] + 1;
                    ans--;  // 왜냐면 처음 시작을 1로 했으니까..... 
                    printf("%d", ans);
                    return 0;
                }
                else {
                    ddg_vt[new_r][new_c] = ddg_vt[cur_ddg.first][cur_ddg.second] + 1;
                    ddg_q.push(pii(new_r, new_c));
                }
            }
        }

    } 
    // 답을 출력 
    printf("KAKTUS");
}
}

3. C++ - 공간 복잡도 해결