미로찾기 + 길막기

_ : 길, # : 벽, S : 출발지, T : 도착지

 

출발지 -> 도착지로 가는길에서 벽 하나로 길을 막을수 있는 좌표를 찍으시오.
상하좌우로만 움직이며, 좌측하단은 1,1로 시작한다.

------------

해당문제를 어떤식으로 풀지 고민을 했다.
1. 입력값이 _, #, S, T 이니 1, 0, 출발지, 도착지 값을 구한다 (이때 출발, 도착지도 1로 표시)
2. 0과 1로 이루어진 2차원 배열로 BFS로 갈수있는 경우의 수를 구한다
3. 해당 값으로 경우의 수가 2이상부터 max값까지 모든 칸의 경우의 수를 구해서 하나씩 0으로 바꾸고
바꾸었을때 도착 불가능한 것만 체크 하는 식으로 하였다.

코드는 의식의 흐름대로 짜서 최적화 및 변수명 등 꼬여서,,,스파게티 소스

import copy
import time
from pprint import pprint

def _zeroone(n, m, array):
	'''S,T,_,#을 숫자로 바꾸는 작업'''
    for i in range(n):
        for j in range(m):
            if array[i][j] == '_':
                array[i][j] = 1
            elif array[i][j] == '#':
                array[i][j] = 0
            elif array[i][j] == 'S':
                start = [i,j]
                array[i][j] = 1
            elif array[i][j] == 'T':
                end = [i,j]
                array[i][j] = 1

    return array, start, end


def solve(start, end, lines):
	''' bfs로 모든 경우의 수를 구한 리스트 리턴 '''
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    next_pos = []
    next_pos.append(start)
    while next_pos:
        x, y = next_pos.pop(0)
        value = lines[x][y]
        for i in range(4):
            tmp_x = x + dx[i]
            tmp_y = y + dy[i]

            if tmp_x < 0 or tmp_y < 0 or tmp_x >= N or tmp_y >= M:
                continue

            tmp_value = lines[tmp_x][tmp_y]

            if tmp_value < 1:
                continue

            if tmp_value == 1 or value + 1 < tmp_value:
                lines[tmp_x][tmp_y] = value + 1
                next_pos.append((tmp_x, tmp_y))
    return lines

def RBFS():
	'''특정 칸을 0 즉 벽으로 만들었을때 도착 가능 여부'''
    queue = [start]
    visited[start[0]][start[1]] = 1
    while queue:
        x, y = queue.pop(0)
        if x == end[0] and y == end[1]:
            # 최종 경로 도착
            return 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 0 and b[nx][ny] == 1:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))
    else:
        return 1


def _remake(n, m, array, k):
    '''x,y, 배열, 변환할 값'''
    array[k[1]][k[2]] = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] > 1:
            	array[i][j] = 1
    return array

def _count(N, M, array):
	''' 최대값 및 좌표값 가져오기'''
    max_nu = []
    for i in array:
        max_nu.append(max(i))
    max_num = max((max_nu))
    aaa = []
    for m_num in range(2, max_num):
        for i in range(N):
            for j in range(M):
                if i == end[0] and j == end[1]:
                    continue
                if array[i][j] == m_num:
                    aaa.append((m_num, i, j))
    return aaa

def read_data():
	''' 입력값 파일로 읽음 '''
    f = open("1.inp", "r")
    ret = f.readlines()
    f.close()
    return ret


def print_data(answer):
	''' 파일로 출력'''
    f = open("1.out", "w")
    f.write(f"{count}\n")
    answer.sort()
    for i in answer:
        f.write(f"{i[0]} {i[1]}\n")

    f.close()

if __name__ == '__main__':
    #1이 지날수 있는 경로, 0이 막힌 벽
    start_time = time.time()
    #직접입력을 원하는경우 92~95번째 주석 해제
    data = read_data()
    N,M = map(int, data[0].split())
    graph = []
    for i in data[1:]:
        graph.append(list(i.strip()))
    answer = []
    count = 0
    try:
        matrix, start, end = _zeroone(N, M, graph)
        visited = [[0]*M for _ in range(N)]
        dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
        result1 = solve(start, end, matrix)
        result1[start[0]][start[1]] = 1

        #경로 하나씩 막기
        if result1[end[0]][end[1]] == 1:
            print_data(answer)
        else:
            b = copy.deepcopy(result1)
            block_num = _count(N, M, b)
            for i in block_num:
                b = copy.deepcopy(result1)
                b = _remake(N, M, b, i)
                visited = [[0] * M for _ in range(N)]
                result = RBFS()
                if result != 0:
                    count += 1
                    answer.append((i[2]+1, M-i[1]))
            print_data(answer)
    except:
        print_data(answer)

 

변수명도 더럽고 코드도 최적화는 안되었다.,,,,