[SWEA 코딩] S/W 문제해결 기본 미로1 - PYTHON #1226

소스 코드

def bfs(ii,jj):
 
    check = 0
 
    temp = [[ii,jj]]
 
    # 방문 표시
    visited[ii][jj] = 1
 
    # 계속 반복
    while True:
        i_idx, j_idx = temp.pop(0)
 
        for e in range(4):
            ni = i_idx+x[e]
            nj = j_idx+y[e]
 
            # index 범위 안에 있고
            if 0 <= ni < 16 and 0 <= nj < 16:
 
                # 이동할 곳이 길이며, 방문한 적이 없는 경우
                if maze[ni][nj] == 0 and visited[ni][nj] == 0:
                    temp.append([ni,nj])
                    visited[ni][nj] = 1
 
                # 도착점이면 탈출
                elif maze[ni][nj] == 3:
                    check = 1
                    break
        
        # 도착점에 도착했거나 더 이상 이동하지 못하게 되었을 때
        if check == 1 or len(temp) == 0:
            break
 
    return check
 
x = [-1,1,0,0]
y = [0,0,-1,1]
 
 
for t in range(10):
    tc = int(input())
 
    # 미로
    maze = [list(map(int,input())) for _ in range(16)]
 
    # 방문 확인용
    visited = [[0]*16 for _ in range(16)]
 
    i = -1
    j = -1
 
    for q in range(16):
        for w in range(16):
            
            # 출발점 찾기
            if maze[q][w] == 2:
                i = q
                j = w
                break
 
        if i != -1:
            break
 
    res = bfs(i,j)
 
    print('#{} {}'.format(tc,res))

 

---

해결 방법

1. 미로의 크기가 16*16이기 때문에 dfs로는 어렵다고 판단

 

2. bfs로 문제 해결

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.