https://school.programmers.co.kr/learn/courses/30/lessons/1844
백트래킹?? dfs?? bfs??
일단 2차원배열 동서남북이니까 x,y 이동을 따로 리스트로 만들어야겠다고 생각
처음엔 무조건 dfs로 풀어봐야지~ 하고 해봤는데 답이 잘 안나오는 듯했다. 질문하기를 보니 BFS를 푸는 것같다.
맵의 최단경로같은거 구할 때는 BFS 생각해보기...
근데 bfs 툴은 외워서 쓰겠는데 그래서 이걸 어떻게하지? 생각 뿐
from collections import deque
def bfs(graph, start, visited):
queue = dequeue([start])
visited[start] = True
while queue:
v = queue.popleft()
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
def solution(maps):
answer = 0
# 최단 경로, 백트래킹?
n,m = len(maps), len(maps[0])
dx = [-1,1,0,0] # 동 서 남 북
dy = [0,0,1,-1] # 동 서 남 북
visited = [[False] * m for _ in range(n)]
return answer 결국 구글링의 도움 ㄱㄱㄱㄱ...
2차원배열이라 튜플형태를 활용하는 듯했다.
from collections import deque # queue 라이브러리 삽입
def bfs(maps, visited, n, m):
if not maps[n - 2][m - 1]: #다 막혀있는 곳이면
return -1
queue = deque([(0, 0)]) # 현재 위치
visited[0][0] = True # 방문 처리
dx = [-1,1,0,0] # 동 서 남 북
dy = [0,0,1,-1] # 동 서 남 북
while queue:
y, x = queue.popleft()
for i in range(4): # 동서남북
nx = x + dx[i] # 가게 될 위치를 계산 (열)
ny = y + dy[i] # 행
# 갈 수 있는 방향이고 면적을 벗어나지 않는 경우
if 0 <= nx < m and 0 <= ny < n and maps[ny][nx]:
if not visited[ny][nx]:
visited[ny][nx] = True # 방문처리
queue.append((ny, nx)) # 큐 삽입
maps[ny][nx] = maps[y][x] + 1 # 최단경로 갱신
return maps[n - 1][m - 1]
def solution(maps):
n,m = len(maps), len(maps[0])
visited = [[False] * m for _ in range(n)]
answer = bfs(maps, visited, n, m)
return answer
근데 무엇인가 통과가 안되고있다...
일단 효율성에서도 통과가 안되었고 ㅠ
결과에서도 실패가 떠서 단순히 시간초과 문제가 아닌듯
벽에 다 막혀있는 경우를 제대로 고려하지않아서인가 싶어서 좀 더 고쳐보았다.
from collections import deque # queue 라이브러리 삽입
def bfs(maps, visited, n, m):
if (not maps[n - 2][m - 1]) and
(not maps[n-2][m-2]) and (not maps[n-1][m-2]): #다 막힘
return -1
queue = deque([(0, 0)]) # 현재 위치
visited[0][0] = True # 방문 처리
dx = [-1,1,0,0] # 동 서 남 북
dy = [0,0,1,-1] # 동 서 남 북
while queue:
y, x = queue.popleft()
for i in range(4): # 동서남북
nx = x + dx[i] # 가게 될 위치를 계산 (열)
ny = y + dy[i] # 행
# 갈 수 있는 방향이고 면적을 벗어나지 않는 경우
if 0 <= nx < m and 0 <= ny < n and maps[ny][nx]:
if not visited[ny][nx]:
visited[ny][nx] = True # 방문처리
queue.append((ny, nx)) # 큐 삽입
maps[ny][nx] = maps[y][x] + 1 # 최단경로 갱신
return maps[n - 1][m - 1]
def solution(maps):
n,m = len(maps), len(maps[0])
visited = [[False] * m for _ in range(n)]
answer = bfs(maps, visited, n, m)
return answer
효율성은 다 통과가 되었으나 실행평가에서 아직도 막혔음
질문하기를 보니까 상대측 진영에서 벽으로 다 막히지않아도 도달하지못할 수도 있는 것을 고려해야함
그러면 내 쪽에서 벽이 생겼나??? 너무 단순하게 (0,1), (1,0) 쪽만 막히면 되나? 싶어서 조건을 걸었는데 런타임 에러나는 테스트 케이스도 있었다.
근데 조건을 보니까 n,m이 1인 경우는 없다고 한다.
그러면 최단경로의 거리는 최소 1보단 커야한다. (동서남북이니까 대각선은 못할테고)
그래서 만약 구한 경로의 길이가 1이면 안된다고 생각하고 return -1로 해볼까? 했는데 통과가 되었다;;; 이게 되네
코드를 더 다듬으려고 보니, 그럼 굳이 상대측 진영 근처도 막혀있는지 확인안해도 될 것같아서 지우고 돌려보니 통과가 된다.
from collections import deque # queue 라이브러리 삽입
def bfs(maps, visited, n, m):
queue = deque([(0, 0)]) # 현재 위치
visited[0][0] = True # 방문 처리
dx = [-1,1,0,0] # 동 서 남 북
dy = [0,0,1,-1] # 동 서 남 북
while queue:
y, x = queue.popleft()
for i in range(4): # 동서남북
nx = x + dx[i] # 가게 될 위치를 계산 (열)
ny = y + dy[i] # 행
# 갈 수 있는 방향이고 면적을 벗어나지 않는 경우
if 0 <= nx < m and 0 <= ny < n and maps[ny][nx]:
if not visited[ny][nx]:
visited[ny][nx] = True # 방문처리
queue.append((ny, nx)) # 큐 삽입
maps[ny][nx] = maps[y][x] + 1 # 최단경로 갱신
return maps[n - 1][m - 1]
def solution(maps):
n,m = len(maps), len(maps[0])
visited = [[False] * m for _ in range(n)]
answer = bfs(maps, visited, n, m)
if answer == 1 :
return -1
return answer
.gif)