[bfs/백준] 6593번 : 상범 빌딩

- 문제 : https://www.acmicpc.net/problem/6593

 

Gold Lv5 문제이고, 답없이 풀었다. 

기본 bfs 문제에서 행렬이 3차원으로만 바뀐 건데 전체 행렬 입력받는데 인덱스를 잘못 설정해 IndexError가 많이 발생해서 시간이 좀 걸렸다. 

 

문제 이해 

- 여러 테스트케이스가 주어지고, 각 케이스마다 l, c, r 값이 주어지는데 2차원 행렬이 l개씩 입력된다. 

- 입력된 3차원 행렬들을 가지고 ' . '인 지점으로 탐색하면서 S에서 시작해 E로 가는 최소 경로 수를 출력한다. 

- 주의해야할 점이 총 3가지가 있다. 이거를 생각 안해서 IndexError로 헤맸다.

1. 인덱스 값을 주의해야 한다. matrix[a][b][c]는 a 층의 행렬의 b행 c열을 의미한다. 이를 x, y, z로 바꾸면 z, x, y가 된다. 

2. 위, 아래, 상, 하, 좌, 우 로 움직이므로 총 6개의 이동이있어서 dc, da, db를 다음과 같이 정의해야한다. 처음에dc = [-1, 1]로 설정했는데 이렇게 하면 대각선 위아래로 움직이므로 틀린 움직임 된다. 그래서 세 개의 배열 모두 길이 6이어야 한다.

dc, da, db = [-1, 1, 0, 0, 0, 0], [0, 0, -1, 1, 0, 0], [0, 0, 0, 0, -1, 1]

3. 마지막으로는 처음에 주어지는 값들이다. 빈칸 없이 연속으로 리스트가 주어지는 것이 아닌 i층이 끝나면 마지막에 아무것도 없는 빈줄이 입력되는데, 이를 고려해서 처음에 matrix를 입력 받을 때 r이 아닌 (r + 1)로 받아야지 IndexError가 발생하지 않는다.

 

풀이 로직 

- l, r, c 값을 입력 받은 다음 l 번씩 (r + 1)을 받아서 matrix를 입력받는다. 

- matrix 값 중에서 S와 E의 위치를 찾는다.

- S 위치를 시작으로 bfs를 진행한다. 

- 탐색은 행렬 범위 내에 방문하지 않았고 ' . ' 또는 'E' 값인 지점으로 하면 된다.

- visit[z][x][y]의 값을 기준으로 0이라면 S에서 E로 못간 것이므로 'Trapped!'를 출력해주고, 0이 아니라면 visit[z][x][y] - 1을 포함한 문장을 출력해준다. (S를 방문처리하기 위해 시작을 1로 했기에 정답과 1 차이가 나서 빼줬다)

 

정답 풀이 

- bfs 

def bfs(c, a, b, matrix, visit, z, x, y):
    visit[c][a][b] = 1
    queue = [[c, a, b]]
    dc, da, db = [-1, 1, 0, 0, 0, 0], [0, 0, -1, 1, 0, 0], [0, 0, 0, 0, -1, 1]
    e, f, g = len(matrix), len(matrix[0]), len(matrix[0][0])
    
    while queue:
        c, a, b = queue.pop(0)
        
        if c == z and a == x and b == y:
            return visit[z][x][y]
        
        for i in range(6):
            nc, na, nb = c + dc[i], a + da[i], b + db[i]
            if 0 <= nc < e and 0 <= na < f and 0 <= nb < g:
                if not visit[nc][na][nb] :
                    if (matrix[nc][na][nb] == '.' or matrix[nc][na][nb] == 'E'):
                        visit[nc][na][nb] = visit[c][a][b] + 1
                        queue.append([nc, na, nb])
                        
    return visit[z][x][y]

 

- 주어진 matrix 만들고 S 와 E의 위치 구하기 

while True:
    first, second, third = map(int, input().split())
    
    if first == 0 and second == 0 and third == 0:
        break
    
    c, a, b = 0, 0, 0
    z, x, y = 0, 0, 0
    matrix = [[] for _ in range(first)]
    for i in range(first):
        for j in range(second + 1): # 한 층 다음에 오는 빈칸 때문에 IndexError 계속 발생함
            temp = list(input())
            if len(temp) != 0:
                matrix[i].append(temp)
            else:
                continue
                 
    times = 0
    for i in range(first):
        for j in range(second):
            for k in range(third):
                if times == 2:
                    break
                if matrix[i][j][k] == 'S':
                    c, a, b = i, j, k # z, x, y
                    times += 1
                if matrix[i][j][k] == 'E':
                    z, x, y = i, j, k
                    times += 1

 

- 전체 코드 

def bfs(c, a, b, matrix, visit, z, x, y):
    visit[c][a][b] = 1
    queue = [[c, a, b]]
    dc, da, db = [-1, 1, 0, 0, 0, 0], [0, 0, -1, 1, 0, 0], [0, 0, 0, 0, -1, 1]
    e, f, g = len(matrix), len(matrix[0]), len(matrix[0][0])
    
    while queue:
        c, a, b = queue.pop(0)
        
        if c == z and a == x and b == y:
            return visit[z][x][y]
        
        for i in range(6):
            nc, na, nb = c + dc[i], a + da[i], b + db[i]
            if 0 <= nc < e and 0 <= na < f and 0 <= nb < g:
                if not visit[nc][na][nb] :
                    if (matrix[nc][na][nb] == '.' or matrix[nc][na][nb] == 'E'):
                        visit[nc][na][nb] = visit[c][a][b] + 1
                        queue.append([nc, na, nb])
                        
    return visit[z][x][y]                   
    
while True:
    first, second, third = map(int, input().split())
    
    if first == 0 and second == 0 and third == 0:
        break
    
    c, a, b = 0, 0, 0
    z, x, y = 0, 0, 0
    matrix = [[] for _ in range(first)]
    for i in range(first):
        for j in range(second + 1): # 한 층 다음에 오는 빈칸 때문에 IndexError 계속 발생함
            temp = list(input())
            if len(temp) != 0:
                matrix[i].append(temp)
            else:
                continue
                 
    times = 0
    for i in range(first):
        for j in range(second):
            for k in range(third):
                if times == 2:
                    break
                if matrix[i][j][k] == 'S':
                    c, a, b = i, j, k # z, x, y
                    times += 1
                if matrix[i][j][k] == 'E':
                    z, x, y = i, j, k
                    times += 1   
    
    visit = [[[0] * third for _ in range(second)] for _ in range(first)]
    answer = bfs(c, a, b, matrix, visit, z, x, y)
    
    if answer == 0:
        print('Trapped!')
    else:
        print('Escaped in ' + str(answer - 1) + ' minute(s).')

 

삽질한 기록,,,