다 필요없고 BFS 핵심
0. BFS는 재귀 X이다.
1. 따라서 BFS 안에 큐 생성한다
2. 시작 포인트 일단 넣는다
3. while queue
4. 현위치 = popleft()
5. for 다음위치(또는 다음 노드) 가져와
6. 다음 위치가 조건에 맞으면(또는 방문 안했으면) 이동시켜
7. queue.append(다음위치) <--- 개중요 (for안에 넣어서 다음위치/이웃노드 전부 넣어주는)- 그리고 DFS 문제든 BFS 문제든 방문 기록을 활용하는 방식으로,
- "방문 기록"을 남기는 방향으로 문제를 푸는 유형이다 라고 생각하면 될거같다.
- 내가 잘못 푼 경우인데, 이 경우 DFS가 되어서
- 잘 가다가 상하좌우가 전부 1일 때 내가 dx, dy 설정을 한 순서대로 타고 내려감
- 뭔 소리냐면, [좌, 하, 우, 상] 으로 설정했기 때문에
여기서 4열 맨 오른쪽에서 '하'로 안가고, DFS라서 '좌'로 계속 타고 내려감
=> 정답이 안됨
- 뭔 소리냐면, [좌, 하, 우, 상] 으로 설정했기 때문에
''' 내가 풀다 만 - 잘못된 풀이 (실패작) '''
def dfs(n, m, y, x, graph, cnt):
graph[y][x] = 0 # visit처리
# 좌 하 우 상
dy = [0, 1, 0, -1]
dx = [-1, 0, 1, 0]
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if ny == n and nx == m:
break
if 0 <= ny and ny < n and 0 <= nx and nx < m:
if graph[ny][nx] == 1:
cnt += 1
cnt = dfs(n, m, ny, nx, graph, cnt)
return cnt
def sol(n, m, graph):
cnt = 0
cnt = dfs(n, m, 0, 0, graph, cnt)
cnt += 2 # 시작노드와 끝노드 더해줌
return cnt
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
print(sol(n, m, graph))
동빈나 솔루션 정리
- (1,1)부터 BFS를 활용하여 최단 거리를 기록하면 해답을 얻을 수 있다!
''' 다시 풀어보자 => BFS로 가야해, BFS가 핵심이야! DFS하면 안돼! '''
# BFS는 회귀가 아니고 while - for를 사용한다
from collections import deque
def BFS(y, x, graph):
queue = deque()
queue.append((x, y)) # (중요) 1. BFS는 맨첨에 방문할걸 일단 넣는다 -> 큐에
# 좌 하 우 상
dy = [0, 1, 0, -1]
dx = [-1, 0, 1, 0]
while queue:
x, y = queue.popleft() # (중요) 2. BFS는 일단 뺀다 (= 얘의 이웃 가자)
''' [현 위치에서의 BFS 수행] '''
for i in range(4):
# (중요) 3. 이웃 계산 = 다음 이동할 위치 계산
ny = y + dy[i]
nx = x + dx[i]
# 범위 밖으로 나갈 경우 -> 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 이동 후 0일 경우 -> 무시
if graph[nx][ny] == 0:
continue
# 이동 후 1일 경우 -> 이전거 + 1
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny)) # (개중요) 4. 이동 했으면 이동한 놈을 넣는다
# BFS 전체를 끝내버린 후 그래프 마지막 위치의 값만 리턴하면 됨
return graph[n-1][m-1]
print(BFS(0, 0, [[1, 0, 1, 0, 1, 0],
[1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1]]))실행결과 보기 - BFS로 진행해야 한다
''' 다시 풀어보자 => BFS로 가야해, BFS가 핵심이야! DFS하면 안돼! '''
# BFS는 회귀가 아니고 while - for를 사용한다
from collections import deque
def BFS(y, x, graph):
queue = deque()
queue.append((x, y)) # (중요) 1. BFS는 맨첨에 방문할걸 일단 넣는다 -> 큐에
# 좌 하 우 상
dy = [0, 1, 0, -1]
dx = [-1, 0, 1, 0]
while queue:
print(graph[0])
print(graph[1])
print(graph[2])
print(graph[3])
print(graph[4])
print('------------------')
x, y = queue.popleft() # (중요) 2. BFS는 일단 뺀다 (= 얘의 이웃 가자)
''' [현 위치에서의 BFS 수행] '''
for i in range(4):
# (중요) 3. 이웃 계산 = 다음 이동할 위치 계산
ny = y + dy[i]
nx = x + dx[i]
# 범위 밖으로 나갈 경우 -> 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 이동 후 0일 경우 -> 무시
if graph[nx][ny] == 0:
continue
# 이동 후 1일 경우 -> 이전거 + 1
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny)) # (개중요) 4. 이동 했으면 이동한 놈을 넣는다
# BFS 전체를 끝내버린 후 그래프 마지막 위치의 값만 리턴하면 됨
return graph[n-1][m-1]
print(BFS(0, 0, [[1, 0, 1, 0, 1, 0],
[1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1]]))
- 이런 느낌임 (참고로 여기서 끝난게 아니고 아래처럼 끝까지 가긴 함)
- 그래서 마지막까지 loop 끝나면 return graph[n-1][m-1] 을 해주는 것
- 그래서 마지막까지 loop 끝나면 return graph[n-1][m-1] 을 해주는 것
아무튼 핵심
0. BFS는 재귀 X이다.
1. 따라서 BFS 안에 큐 생성한다
2. 시작 포인트 일단 넣는다
3. while queue
4. 현위치 = popleft()
5. for 다음위치(또는 다음 노드) 가져와
6. 다음 위치가 조건에 맞으면(또는 방문 안했으면) 이동시켜
7. queue.append(다음위치) <--- 개중요 (for안에 넣어서 다음위치/이웃노드 전부 넣어주는)
Do My Best
DFS가 좌측하단으로 CNT하기 때문에 우측하단으로 내려가서 정답을 구할 수 없다고 하셨는데 그럼 BFS풀이처럼 누적해서 지나가면 좌측하단으로 갔다가 우측하단으로 가서 답은 같은 거 아닌가요?