본문 바로가기

BFS16

[ 파이썬(python) ] 백준 2468 - 안전 영역 📌 백준 2468 - 안전 영역 문제 설명 💡 나의 풀이 문제를 이해하는 데는 어렵지 않았지만, 구현하는데 나름대로 어려웠던 문제였다. 아직 구현 실력이 뛰어나지 않아서 그런 것 같다. N의 최대 범위가 100 * 100이어서 시간 복잡도가 O(N^3)이어도 시간초과가 나지 않을 것이라고 판단했는데, 같은 지역에서 내리는 비의 양에 따른 모든 경우를 조사해야 하기 때문에 이중 반복문에서 삼중 반복문으로 늘어났다. 모든 높이를 조사할때는 입력값 중 가장 작은 값부터 가장 큰 값을 범위로 잡았다. 여기서 pythonic코드를 배웠는데 2차원의 배열에서 min, max값을 찾을 때 map함수를 사용하면 간단하게 출력할 수 있다. 반복문 안에서 가장 큰 값의 범위를 설정할 때는 +1을 해주자 아니면 오답 판정 .. 2021. 4. 19.
[ 파이썬(python) ] 백준 2667 - 단지번호붙이기 📌 백준 2667 - 단지번호붙이기 문제 설명 💡 나의 풀이 아침부터 저녁까지 이 문제만 잡고 늘어졌는데 드디어 풀었다. 😇 😇 특히, 처음에 방문한 좌표를 1로 선언한 이유와, 새로운 좌표를 1로 선언한 이유를 잘 몰라서 엄청 헤맸다. 이 문제는 BFS, DFS 파트에 약한 나에게 많은 도움을 준 문제다. 또, BFS와 DFS로 풀 수 있는데 지금은 BFS버전이고 내일은 DFS로 풀어봐야겠다. 푸는 방법으로 append와 flag방식 두 개로 나눠서 풀었는데 flag 실행시간이 append 보다 4ms정도 더 빨랐다.( 4ms면 별 의미 없는 시간차이긴 하지만, True, False가 근소하게 더 빠르다는 것을 참고적으로 알아두자!) 개별 단지수를 구하는 코드는 고민을 많이 했는데, 결론적으로 {}를 .. 2021. 4. 16.
[ 파이썬(python) ] 백준 1260 - DFS와 BFS 📌 백준 1260 - DFS와 BFS 문제 설명 💡 나의 풀이 BFS와 DFS를 둘 다 사용해야 하는 문제인데 풀이 방법은 다음과 같다. 문제에서 정점 번호가 작은 것을 먼저 방문한다.를 통해 입력값을 인접리스트(adjacent list)으로 넣을 때 sort를 붙여 작은 값부터 들어가게끔 설정했다. dfs의 구현 순서는 다음과 같다. 처음 들어온 값 index의 flag를 True로 바꾼다. 만약, 인접 노드를 방문하지 않았다면(flag = False), 해당 인접노드로 들어가서 방문하지 않은 인접 노드가 없을 때까지 들어간다.(recursive) 재귀문을 탈출하면서 해당 값을 하나씩 출력한다. bfs의 구현순서는 다음과 같다. 처음 들어온 값을 queue에 넣는다. 처음 들어온 값 index의 fla.. 2021. 4. 16.
[ 파이썬(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.
[ 파이썬(python) ] 코드업 4503 - 바이러스(BFS) 📌 코드업 4503 - 바이러스(BFS) 문제 설명 💡 나의 풀이 어제 풀었던 문제를 BFS로 풀어봤다. DFS는 한 노드에서 인접 노드가 더 없을 때까지 끝까지 파고 들어가는데, BFS는 한 노드에서 인접노드가 없으면 주변 인접 노드를 찾는다. BFS는 Queue를 이용해서 풀면 되는데, 어제처럼 flag, check형식으로 풀어보자. BFS방식의 전체적인 흐름은 다음과 같다.(Queue는 선입선출임을 기억하자.) 시작하는 값을 Queue에 넣고 방문처리를 한다. Queue안에 현재 들어있는 값(노드)을 뺀다. 해당 노드의 인접한 노드 중에서 아직 방문하지 않은 노드를 모두 큐에 넣는다. 2~3번의 과정을 더 이상 할 수 없을 때까지 반복한다. Flag, Check방식은 다음과 같다. Flag C와 동.. 2021. 4. 15.

티스토리툴바