Python으로 푸는 SW Expert Academy 1227. 미로2

SW Expert Academy 1227. 미로2

미로에서 시작 점부터 도착점으로 표시된 지점까지

갈 수 있는 길이 있는지 판단하는 프로그램을 작성해야 한다.

이 문제는 <1226. 미로1> 문제와 규모만 다를 뿐 같은 문제이며

<1226. 미로 1> 에서 주어지는 1차원 배열의 크기가 커지더라도

문제가 없도록 코드를 잘 짰다면 무난하게 통과할 수 있다.

SW Expert Academy 1226. 미로1 풀이 보기

삼성 SW Expert Academy에서 푼 문제 보기

github에서 코드 보기

문제 조건

상하좌우로 이동이 가능하다.

시작 지점에서 도착지점까지 도달이 가능한지 여부만 반환하면 된다.

문제 풀이

도달할 수 있는 모든 지점을 확인하면 된다. 아마 시간 초과를 막기 위해서는 벽인지 아닌지만 구분해서 길일 경우에 그게 도착지점(3)인지를 확인하면 된다.

이미 한번 확인한 지점을 다시 재확인 하지 않도록 짜는게 가장 큰 핵심인 것 같다. 한 두칸은 괜찮지만 만약 지나온 길인지를 체크해두지 않았을 경우에

길이 서로 모두 이어져 있을 경우에는 불필요한 체크를 반복할 수 있다. 나는 <미로 1>에서 코드를 잘 짜두어서 배열의 크기만 100으로 늘려주었다.

파이썬 코드

from collections import deque
 
 
def solve(start, goal, lines):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    next_pos = deque([])
 
    sx, sy = start
    if lines[sx][sy] == 3:
        return True
 
    next_pos.append(start)
    while next_pos:
        start = next_pos.popleft()
        sx, sy = start
 
        # already visited
        if lines[sx][sy] == 7:
            continue
        
        lines[sx][sy] = 7
 
        # check around routes  
        for i in range(4):
            temp_x = sx + dx[i]
            temp_y = sy + dy[i]
 
            # Out of range
            if temp_x < 0 or temp_y < 0 or temp_x >= 100 or temp_y >= 100:
                continue
            
            value = lines[temp_x][temp_y]
                        
            if value == 3:
                return True
 
            if value == 7:
                continue
 
            if value == 0:
                next_pos.append((temp_x, temp_y))
    return False
 
 
if __name__ == "__main__":
    for t in range(1, 11):
        input()
        lines = []
        start = None
        goal = None
        result = 0
        for i in range(100):
            line = list(map(int, list(input().strip())))
            lines.append(line)
 
            if 2 in line:
                start = (i, line.index(2))
            if 3 in line:
                goal = (i, line.index(3))
 
        visited = []
        if solve(start, goal, lines):
            result = 1
        
        print("#{0} {1}".format(t, result))

#1227 미로2 #python 1227 미로2 #파이썬 1227 미로2 #sw expert 1227 미로2 #sw expert 미로2