[ 파이썬(python) ] 이것이 코딩 테스트다 - 음료수 얼려먹기(DFS)
📌 이것이 코딩 테스트다 - 음료수 얼려먹기 영상 링크(42:48) 💡 나의 풀이 DFS로 문제를 해결 할 수 있는데, 0인 값이 상, 하, 좌, 우로 연결되어 있는 노드를 묶으면 된다. BFS, DFS는 조건 설정이 중요한 것 같다. 특정한 지점의 주변 상, 하, 좌, 우를 살펴보고 주변 지점 중 값이 0이면서 아직 방문하지 않은 지점이 있으면 해당 지점을 방문한다. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다. 1~2번의 과정을 모든 노드에 반복하고, 방문하지 않은 지점의 수를 센다. ''' 4 5 00110 00011 11111 00000 ''' ''' 15 14 00000111100000 11111101111110 11011101..
2021. 4. 15.
[ 파이썬(python) ] 이것이 코딩 테스트다 - 미로 탈출(BFS)
📌 이것이 코딩테스트다 - 미로 탈출 영상 링크(51:30) 💡 나의 풀이 BFS를 이용하는 흐름을 알아야 풀 수 있었는데, 그 흐름을 잘 몰라서 못 풀었다. 이전까지는 입력값을 그래프로 변환해서 풀었는데, 입력값이 이중 리스트일때는 어떻게 줘야 할지 감이 잘 잡히지 않았다. 또, BFS문제를 풀어보니까 값이 어떻게 바뀌는지 흐름을 잡는것이 중요하다고 느꼈다. from collections import deque n, m = map(int, input().split()) graph = [list(map(int, input())) for _ in range(n)] # 상하좌우 선언 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): queue = deque() ..
2021. 4. 15.
