[TIL] 20240317 개발일지

벽 부수고 이동하기

N*M
0은 이동할 수 있는 곳
1은 이동할 수 없는 곳

1,1에서 N, M까지 이동할 때 최단 경로
시작점과 도착점도 센다

출력 : 이동할 때 걸리는 최단 거리


6 4
0100
1110
1000
0000
0111
0000

치즈

- 입력
첫 번째 줄 : n m
  n : 세로
  m : 가로


- 출력 
첫 번째 줄 : 치즈가 모두 녹아서 없어지는데 걸리는 시간
두 번쨰 줄 : 모두 녹기 한 시간 적에 남아 있는 치즈 조각 칸 수 

13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

 

 

 

보물섬

엊그제 풀다가 틀려서 다시 봤는데 방문 배열의 선언 위치가 잘못되어 틀린 것이었다..

 

 

 

deque 문제
얼마전 JS에서도 동일한 문제를 겪었는데, 파이썬에서 queue를 사용할 때 list를 사용하고 pop(0)를 통해서 뺄 수 있다는 포스트를 보았다.

문제는 pop(0)를 이용하면 인덱싱이 다시 일어나야하므로 O(N)의 시간 복잡도를 가지기 때문에 일반적인 문제에서 시간초과가 발생할 수 밖에 없다.

python은 js와 달리 deque()를 제공하기 때문에 이를 사용한다면 쉽게 풀 수 있다.