[백준] 6593 상범빌딩, python, C++

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

6593번: 상범 빌딩

 

import sys;input = sys.stdin.readline
from collections import deque

# 탐색
def bfs(start, end, size, building):
    q = deque()
    q.append(start)
    visit = [[[0 for k in range(size[2] + 2)] for j in range(size[1] + 2)] for i in range(size[0] + 2)]
    # 0일때 continue 하기위해서 1로 시작, bfs 끝나면 리턴 값에서 1 뺄것
    visit[start[0]][start[1]][start[2]] = 1
    while q:
        l, r, c = q.popleft()
        for ll, rr, cc in [(1, 0, 0), (-1, 0, 0), (0, 1, 0),(0, -1, 0), (0, 0, 1), (0, 0, -1)]:
            dl, dr, dc = l + ll, r + rr, c + cc
            if building[dl][dr][dc] == '#': continue # 벽
            if visit[dl][dr][dc]: continue # 이미 방문한 점
            visit[dl][dr][dc] = visit[l][r][c] + 1
            q.append((dl, dr, dc))
    if visit[end[0]][end[1]][end[2]]:
        return visit[end[0]][end[1]][end[2]] - 1
    return 0

def main():
    while True:
        # 0 입력
        L, R, C = map(int, input().split())
        if (0, 0, 0) == (L, R, C):
            break

        start, end = None, None
        building = []
        for i in range(L + 2):
            tmp_l = []
            for j in range(R + 2):
                if 0 == j or R + 1 == j or 0 == i or L + 1 == i:
                    tmp_r = "#" * (C + 2)
                else:
                    tmp_r = "#" + input() + "#"
                    for k in range(C + 2):
                        if 'S' == tmp_r[k]:
                            start = [i,j,k]
                        elif 'E' == tmp_r[k]:
                            end = [i,j,k]
                tmp_l.append(tmp_r)
            building.append(tmp_l)
            if 0 != i and L + 1 != i:
                _ = input()
        # 탐색
        answer = bfs(start, end, (L, R, C), building)

        # 출력
        if answer:
            print(f"Escaped in {answer} minute(s).")
        else:
            print("Trapped!")

if __name__ == '__main__':
    main()

최단거리를 탐색해야하므로 3차원 배열에서의 BFS문제이다.

속도를 조금더 높이기 위해 처음 입력할 때 벽('#')을 추가적으로 생성해서 받았다.

조금 까다로웠던 건 입력 중간에 들어오는 공백이었는데 조건문으로 걸어서 처리했다.

나머지는 bfs를 사용해서 진행했고 visit이라는 3차원 행렬을 생성해서 들린 점인지, 얼마나 걸렸는지 확인했다.

또 visit에서 0(false)과 0이 아닌값으로 처리했고 return 할때는 값에 -1을 붙여서 되돌려보냈다.

---

#include<iostream>
#include<vector>
#include<queue>
#include<array>
using namespace std;

int bfs(array<int, 3> start, array<int, 3> end, array<int, 3> size, vector<vector<string>>building) {
	queue<array<int, 3>> q;
	q.push(start);
	q.empty();
	vector<vector<vector<int>>> visit(size[0]+2, vector<vector<int>>(size[1]+2, vector<int>(size[2]+2)));
	visit[start[0]][start[1]][start[2]] = 1;
	int d[6][3] = {{ 1, 0, 0 },{ -1, 0, 0 },{ 0, 1, 0 },{0, -1, 0 },{ 0, 0, 1 },{ 0, 0, -1 }};
	while (!q.empty()) {
		array <int, 3> cur;
		cur = q.front();
		q.pop();
		
		for (int i = 0; i < 6; i++)
		{
			int dl, dr, dc;
			dl = cur[0] + d[i][0];
			dr = cur[1] + d[i][1];
			dc = cur[2] + d[i][2];

			if (building[dl][dr][dc] == '#') continue;
			if (visit[dl][dr][dc]) continue;
			visit[dl][dr][dc] = visit[cur[0]][cur[1]][cur[2]] + 1;
			array <int, 3> tmp = { dl, dr, dc };
			q.push(tmp);

		}
	}
	if (visit[end[0]][end[1]][end[2]]) {
		return visit[end[0]][end[1]][end[2]] - 1;
	}
	return 0;
}

int main() {
	while (1) {
		int L, R, C, answer;
		string remove;
		array<int, 3> start, end, size;
		vector<vector<string>> building;

		cin >> L >> R >> C;
		if (L == 0 && R == 0 && C == 0)			break;
		size = { L, R, C };
		for (int i = 0; i < L+2; i++)
		{
			vector<string> tmp_l;
			for (int j = 0; j < R + 2; j++)
			{
				string tmp_r;
				if (0 == j || R + 1 == j || 0 == i || L + 1 == i) {
					for (int k = 0; k < C + 2; k++)
					{
						tmp_r += "#";
					}
				}
				else {
					string tmp_string;
					cin >> tmp_string;
					tmp_r = "#" + tmp_string + "#";
					for (int k = 0; k < C + 2; k++)
					{
						if ('S' == tmp_r[k]) {
							start = { i,j,k };
						}
						else if ('E' == tmp_r[k]) {
							end = { i,j,k };
						}
					}
				}
				tmp_l.push_back(tmp_r);
			}
			building.push_back(tmp_l);
		}
		answer = bfs(start, end, size, building);

		if (answer) {
			cout << "Escaped in " << answer << " minute(s)." << endl;
		}
		else {
			cout << "Trapped!" << endl;
		}
	}
	return 0;
}

C++에서는 다시 애를 먹었다.

공백(\n)이 들어와도 무시가 되는듯해서 값을 지웠더니 통과했다.

나머지는 파이썬과 동일하다