Python으로 푸는 SW Expert Academy 1226. 미로1

SW Expert Academy 1226. 미로1

문제에서는 미로의 출발점에서 도착점까지 도달할 수 있는지를 확인하도록 구현해야 한다.

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

github에서 코드 보기

문제조건

2는 출발점, 1은 벽, 0은 길이다.

문제 풀이

이동할 수 있는 길이라면 모두 탐색해가며 도착지점(3)에 이를 수 있는지 확인해야 한다.

출발 지점부터 그 주변에 인접한 상하좌우 지점을 모두 확인하고 더이상 방문하지 않은 정점이 없을 때까지 탐색을 진행하는, 너비 우선 탐색(BFS) 문제이다.

while문을 사용해 이동 가능한 다음 지점들을 넣어둔 next_pos 리스트가 모두 비어질 때까지 도착지점(3)이 있는지 탐색을 진행하고

next_pos가 비었는데도 도착지점(3)을 찾지 못했을 경우에는 False를 리턴한다.

파이썬 코드

 
def solve(start, goal, lines):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    next_pos = []
    # 방문 시 7로 표시
 
    sx, sy = start
    if lines[sx][sy] == 3:
        return True
 
    next_pos.append(start)
    while next_pos:
        start = next_pos.pop(0)
        sx, sy = start
 
        # 이미 방문한 곳 패쓰
        if lines[sx][sy] == 7:
            continue
def solve(start, goal, lines):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    next_pos = []
    # 방문 시 7로 표시
 
    sx, sy = start
    if lines[sx][sy] == 3:
        return True
 
    next_pos.append(start)
    while next_pos:
        start = next_pos.pop(0)
        sx, sy = start
 
        # 이미 방문한 곳 패쓰
        if lines[sx][sy] == 7:
            continue
        
        lines[sx][sy] = 7
 
        # 주변 길 탐색    
        for i in range(4):
            temp_x = sx + dx[i]
            temp_y = sy + dy[i]
 
            # 범위 초과 패쓰
            if temp_x < 0 or temp_y < 0 or temp_x >= 16 or temp_y >= 16:
                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(16):
            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))
        
        lines[sx][sy] = 7
 
        # 주변 길 탐색    
        for i in range(4):
            temp_x = sx + dx[i]
            temp_y = sy + dy[i]
 
            # 범위 초과 패쓰
            if temp_x < 0 or temp_y < 0 or temp_x >= 16 or temp_y >= 16:
                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(16):
            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))

#sw expert 1226 #sw expert 1226 미로1 #python sw expert 1226 #sw expert 1226 python #SW Expert Academy 1226 미로1 #파이썬 1226 미로1