글 읽기 - [파이썬] 3차원 배열을 안쓰고 푸는중입니다. 이유를 모르겠습니다..

ckdgnsl1002 2년 전 0

푸는 방법은 주석에 나와있는대로 입니다.

1. 일단 BFS로 안뚫어도 도달은 하는지, 아니면 안뚫으면 못가는지를 확인하고, 그때까지의 방문한 위치 visited 리스트를 반환합니다.

2. 안 뚫으면 못가는 경우

갔던 모든길을 대상으로 1. 상하좌우중 벽이 있고 2. 그 벽 너머의 3방향중 길이 있으며, 갔던 길이 아닌 경우가 있으면 3. 그 벽을 뚫은 새로운 maze를 생성한다.

3. 안뚫어도 성공한 경우

갔던 모든 길을 대상으로 1. 상하좌우중 벽이 있고 2. 그 벽 너머의 3방향중 길이 있고, 갔던 길이라면 +) 둘러쌓여서 간적없는 곳이라면 하나만 뚫어서는 소용이 없기때문. 3. 현재의 길과 너머의 길의 숫자차이를 기록하고, (가장 큰 값 - 2) 만큼 원래 답에서 뺀다.

안뚫어도 성공한 경우의 2번 논리에서 무언가 문제가 있을 것 같은 느낌인데, 구체적으로 파악이 안됩니다...

반례들은 이곳저곳에서 찾아서 해봤는데 다 되었습니다.

# 너비우선탐색 구현하기
# 모든 노드를 깊이순으로 지나기 때문에 가장 먼저 나온 결과가 가장 짧은 길이다.
import sys
from collections import deque
import copy

X, Y = list(map(int, sys.stdin.readline().strip().split()))

first_maze = []

# y축 하나씩 미로를 입력받는다.
for n in range(X):
    first_maze.append(  list(map(int, list(sys.stdin.readline().strip())))  )
    
def BFS(maze):
    # 0으로 초기화
    visited = [[0] * Y for x in range(X)]
    
    # 다음에 어느 노드를 방문할지 쌓아두는 큐
    queue = deque([])
    
    # 시작하는 부분인 (0,0)을 queue및 visited에 추가
    # 아래방향을 x축으로, 오른쪽 방향을 y축으로 하자.
    queue.append([0,0])
    visited[0][0] = 1

    failed_factor = 1
    
    # BFS구현 시작
    while queue:
        cur_x, cur_y = queue.popleft()
        # 만약 지금 뽑은 노드가 최종 목적지 (N , M) 이라면 종료. 
        if cur_x == X-1 and cur_y == Y-1:
            failed_factor = 0
            break
        
        else:
            #왼쪽 (왼쪽으로 갔을 때 인덱스가 0 이상 & visited가 0, maze에서 0)
            if cur_x - 1 >= 0 and visited[cur_x-1][cur_y] == 0 and maze[cur_x-1][cur_y] == 0:
                visited[cur_x-1][cur_y] =visited[cur_x][cur_y] + 1
                queue.append([cur_x-1, cur_y]) 
            
            #오른쪽
            if cur_x + 1 < X and visited[cur_x+1][cur_y] == 0 and maze[cur_x+1][cur_y] == 0:
                visited[cur_x+1][cur_y] =visited[cur_x][cur_y] + 1
                queue.append([cur_x+1, cur_y]) 
                
            #위쪽
            if cur_y+1 < Y and visited[cur_x][cur_y+1] == 0 and maze[cur_x][cur_y+1] == 0:
                visited[cur_x][cur_y+1] =visited[cur_x][cur_y] + 1
                queue.append([cur_x, cur_y+1]) 
            
            #아래쪽
            if cur_y-1 >= 0  and visited[cur_x][cur_y-1] == 0 and maze[cur_x][cur_y-1] == 0:
                visited[cur_x][cur_y-1] =visited[cur_x][cur_y] + 1
                queue.append([cur_x, cur_y-1]) 
                
    if failed_factor == 1:
        return (1, visited)
    
    else:
        return (0, visited, visited[X-1][Y-1])
    


# 안 뚫으면 못가는 경우
# 갔던 모든길을 대상으로 
#   1. 상하좌우중 벽이 있고
#   2. 그 벽 너머의 3방향중 길이 있으며, 갔던 길이 아닌 경우가 있으면 
#   3. 그 벽을 뚫은 새로운 maze를 생성한다.
def break_the_wall(visited):
    new_maze_list = []
    
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    
    for x in range(X):
        for y in range(Y):
            if visited[x][y] != 0:
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<X and 0<=ny<Y and first_maze[nx][ny] == 1:
                        for j in range(4):
                            mx = nx + dx[j]
                            my = ny + dy[j]
                            if 0<=mx<X and 0<=my<Y and first_maze[mx][my] == 0 and visited[mx][my] == 0: # 벽에서 안갔던 곳을 찾으므로 x,y 와 mx, my와 겹칠 수 없음.
                                maze_copy = copy.deepcopy(first_maze)
                                maze_copy[nx][ny] = 0
                                new_maze_list.append(maze_copy)
                                break
            else:
                continue
            
    return new_maze_list


# 안뚫어도 성공한 경우 
# 갔던 모든 길을 대상으로
#   1. 상하좌우중 벽이 있고
#   2. 그 벽 너머의 3방향중 길이 있고, 갔던 길이라면 +) 둘러쌓여서 간적없는 곳이라면 하나만 뚫어서는 소용이 없기때문.
#   3. 현재의 길과 너머의 길의 숫자차이를 기록하고, (가장 큰 값 - 2) 만큼 원래 답에서 뺀다.
# 
def another_way(visited):
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    
    max_diff = 0
    
    for x in range(X):
        for y in range(Y):
            if visited[x][y] != 0:
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<X and 0<=ny<Y and first_maze[nx][ny] == 1:
                        for j in range(4):
                            mx = nx + dx[j]
                            my = ny + dy[j]
                            if 0<=mx<X and 0<=my<Y and first_maze[mx][my] == 0 and visited[mx][my] != 0 and not (mx==x and my==y): #벽 주변의 갔던 길을 찾으므로 x,y와 mx,my가 겹칠 수 있음.
                                diff = visited[mx][my] - visited[x][y]
                                if diff > max_diff:
                                    max_diff = diff
                                
            else:
                continue

    
    return max_diff


# 제대로 시작
# 일단 BFS함수로 첫번째 결과를 얻는다.
first_result = BFS(first_maze)

# 만약 중간에 막혀서 끝났다면
if first_result[0] == 1:
    # break_the_wall 함수로 가능한 모든 경우의 새로운 maze를 얻는다.
    new_maze_list = break_the_wall(first_result[1])
    
    # 최솟값을 찾으므로 가능한 최댓값보다 큰 값을 넣는다.
    answer = X*Y
    
    # 처음 정한 answer말고 새로운 값이 들어갔음을 확인하는 인자
    change_factor = 0
    
    # 새로구한 모든 maze에 대해 BFS를 하고 제일 작은 값을 answer에 대입한다.
    for new_maze in new_maze_list:
        new_result = BFS(new_maze)
        # 오류가 발생하지 않았고
        if new_result[0] == 0:
            change_factor = 1
            # 현재의 answer보다 지금 maze의 최단경로값이 더 작거나 같으면, 값을 대입
            if new_result[-1] < answer:
                    answer = new_result[-1]
                
    if change_factor == 0:
        print(-1)
    else:  
        print(answer)

# 중간에 막힘없이 끝났다면
else:
    # another_way 함수로 나온 결과 - 2 만큼 기존결과에서 뺀다. 
    plus_value = another_way(first_result[1])
    if plus_value >= 2:
        print(first_result[-1] - (another_way(first_result[1])-2))
    else:
        print(first_result[-1])

Green55 2년 전 0

틀린곳을 고쳐도 2. 안 뚫으면 못가는 경우 에서 최악의 경우 O(NM)개의 미로를 만들어봐야해서 시간 내에 돌아갈 수 없을것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 3차원 배열을 안쓰고 푸는중입니다. 이유를 모르겠습니다..

ckdgnsl1002 2년 전 0

Green55 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말