[BOJ/백준 코딩] 이동하기 - PYTHON #11048

소스 코드

def bfs():
    temp = [[0,0]]

    while len(temp) != 0:
        i,j = temp.pop(0)


        for q in range(2):
            N_i = i + x[q]
            N_j = j + y[q]
            if N_i < N and N_j < M:
                if visited[N_i][N_j] < visited[i][j] + maze[N_i][N_j]:
                    visited[N_i][N_j] = visited[i][j] + maze[N_i][N_j]
                    temp.append([N_i,N_j])

    return

# 이동 방향 우, 하
x = [1,0]
y = [0,1]

# N x M
N,M = map(int,input().split())

# 미로
maze = [list(map(int,input().split())) for _ in range(N)]

# 위치의 크기
visited = [[0]*M for _ in range(N)]
visited[0][0] = maze[0][0] + 1

bfs()

print(visited[N-1][M-1]-1)

 

---

해결 방법

1. 이동할 수 있는 경우의 수는 우, 하, 대각선(우하) 3 가지 인데 대각선으로는 이동하지 않아도 됨

(우하 = 우 -> 하 or 하 -> 우 로 이동할 수 있고, 한 번 이동할 때보다 2 번 이동하는 경우가 더 많은 사탕을 획득할 가능성이 높음)

 

2. bfs를 통해 문제를 해결했는데, 오답 처리 됨

 

3. visited[N_i][N_j] < visited[i][j] + maze[N_i][N_j] 코드와 visited[0][0] = maze[0][0] 코드가 문제였음

0,0 위치의 시작 값이 0인 경우에는 잘못 이동하는 것을 확인

ex)

0 0 10

0 0 0

0 0 0

정답은 10이지만, 이동 안 함

그래서 visited[N_i][N_j] <= visited[i][j] + maze[N_i][N_j]로 바꿨더니 시간 초과 발생

 

4. 결국 visited[0][0] = maze[0][0] + 1을 한 후, 출력할 때 1을 빼주기로 함

-> 통과는 했는데 속도가 너무 느렸음

 

5. bfs를 사용하지 않고 다시 코드 작성

-> 0,0에서 오른쪽 방향으로 다 더하고, 아래쪽 방향으로 다 더 한다

ex) maze[0][1] += maze[0][0]

maze[0][2] += maze[0][1]

 

6. 임의의 위치(1,1)의 값은 max(maze[0][1], maze[1][0])임

 

7. 더 빠르게 문제 해결 가능

 

---

느낀 점

비슷한 문제라고 bfs나 dfs로 접근할 필요는 없다.

 

가장 기본적인 방법부터 확인해볼 필요가 있음

 

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

 

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

 

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