1210. [S/W 문제해결 기본] 2일차 - Ladder1

 

BFS를 해결한 풀이로,

문제를 제대로 안 읽어서 시간이 더 소요됐다. 

추적 시작점이 2였다는 것...! 그냥 맨 끝 요소가 타깃인 줄 알았다. 

 

visited를 Set으로 쓰면 조금더 성능이 향상되지 않을까 싶다!

(x, y 의 쓰임이 좌표값과는 다르다.. row, column 값인데 양해 바랍니다...)

def valid(x, y, visited):
    return 0 <= x < total and 0 <= y < total and (x, y) not in visited
 
 
def next_curr(curr, visited):
    move = [(0, 1), (0, -1)]
    for m in move:
        n_x, n_y = curr[0] + m[0], curr[1] + m[1]
        if valid(n_x, n_y, visited) and board[n_x][n_y]:
            return m
    return -1, 0
 
 
def bfs(start):
    q = [start]
    visited = []
    while q:
        curr = q.pop(0)
        if curr[0] == 0:
            return curr[1]
        m_x, m_y = next_curr(curr, visited)
        n_x, n_y = curr[0] + m_x, curr[1] + m_y
        if valid(n_x, n_y, visited):
            q.append((n_x, n_y))
            visited.append((n_x, n_y))
 
 
T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    num = int(input())
    total = 100
    board = []
    for i in range(total):
        board.append([int(x) for x in input().split()])
 
    idx = board[total - 1].index(2)
    start = (total - 1, idx)
    answer = bfs(start)
 
    print(f'#{test_case} {answer}')