BFS Python 문제 BOJ2178 코딩테스트 (4)

 

 

 

목차

 

 

서론

지난 포스팅에서는 BFS를 이용한 개념과 문제를 풀어보았다. 이번 포스팅에서도 백준 BFS 문제인 BOJ2178을 풀어보겠다. 이전과 같이 처음에는 내가 어떻게 풀었는지 적을 것이고, 이후에는 답지를 참고해서 내 것과 비교할 예정이다.

 

---

BOJ 2178 내가 푼 풀이과정 및 코드

 

문제를 보니 최단거리를 찾는 것이다. BFS를 택했다.(사실 BFS 영상에 나온거라 뇌빼고 BFS로 바로 들어가도 되지만 이렇게 접근하는 연습을 하는게 맞다고 판단함.) 최단 경로를 어떻게 접근할까 했다. BFS를 돌며 내가 지나는 칸이 1이면 -> 이전칸 +1을 하고 0이면 안지나 가는 가장 기본적인 툴을 생각했다. 그런데 1도 0도 아닌 값을 만났을 때를 고려해야됐다. 때문에 1이 아닌 칸을 만나면 -> 해당 값과 +1한 값 비교 후 최소값 넣었다. 그게 그 곳을 지나가는 최단거리이기 때문이다. 그리고 마지막으로 마지막 칸에 도달할 수 없는 예외 상황을 넣기 위해 if문으로 graph[n-1][m-1]이 1이나 0이면 -1 출력 아니면 해당 값 출력했다. 오래걸릴 줄 알고 일단 함 처다본다음 밥먹고 마저 풀려했는데, 함 처다봤을 때 다 풀었다. 기본 BFS 툴에서 조금만 바꾸면 되기 때문.

 

from collections import deque

n,m = 4,6 # n행 m열

graph =[

[1,1,0,1,1,0],

[1,1,0,1,1,0],

[1,1,1,1,1,1],

[1,1,1,1,0,1]

]

visited = [[False]*m for _ in range(n)] # queue 돌 때 상하좌우 체크용

queue = deque()

dx = [-1,1,0,0]

dy = [0,0,-1,1]

queue.append((0,0))

visited[0][0] = True

while queue:

    x,y = queue.popleft()

    for k in range(4):

        nx = x + dx[k]

        ny = y + dy[k]

       

        if nx<0 or ny<0 or nx>=n or ny>=m:

            continue

        if visited[nx][ny] or graph[nx][ny] == 0:

            continue

        visited[nx][ny] = True

        if graph[nx][ny] != 1:  #0도, 1도 아닌걸 만나면 둘 중 비교해서 최소값 넣기

            graph[nx][ny] = min(graph[x][y]+1,graph[nx][ny])

        else:  graph[nx][ny] = graph[x][y]+1

        queue.append((nx,ny))

if  graph[n-1][m-1] == 1 or 0:  #마지막 예외상황 체크

    print(-1)

else: print(graph[n-1][m-1])

---

BOJ 2178 정답 체크

내가 보는 유튜브 강의를 참고했다. 일단 +1을 하며 값을 나아가는 건 나와 똑같았다. 그런데 나는 마지막에 0인지 여부를..확인했지만, 유튜브 강의에서는 마지막을 -1로 뒀다. 그러면 굳이 if문이 필요없기 때문. 난 왜 이 생각을 못했지? 이건 풀이 과정인데, Cpp이라 cur이나 fill은 알아들을 수 없다. 아무튼 문제 풀이 흐름과 마지막에 -1넣는 테크닉을 배워야겠다.

---

끝으로

오늘은 BOJ2178을 풀어보았다. 다음에는 BFS 더 어려운 걸 풀어야 되는지, 쉬운 걸 몇 개 더 풀어야 되는 지 고민이 된다. 아니다 나약하면 안되니까 더 어려운걸 풀어봐야겠다. 이름은 쉬워보이지만 딱봐도 힘들어 보이는 BOJ7576번을 풀어볼 예정임. 검색해보니 백준 골드 등급 문제라고 한다. 내힘으로 풀 수 있길 바라며... 다음 포스팅에서 봅시다.