본문 바로가기

BFS16

[ 파이썬(python) ] 백준 1303 - 전쟁 - 전투(BFS) 📌 백준 1303 - 전쟁 - 전투 문제 설명 💡 나의 풀이 (여담이지만 1303 하니까 국방 헬프콜이 생각났다.) 2차원 배열에서 각 색깔에 맞는 거리를 구하는 전형적인 BFS문제이지만, 헷갈린 부분들이 많았다. 한쪽 BFS만 구하는것이 아니고 양쪽 BFS를 모두 구현해야하다보니까 함수를 어떻게 선언하는지 굉장히 고민을 많이 했다. 결론적으로 BFS 함수에 color라는 파라미터를 작성해서 넘겨줬고 함수내에서 각 칸의 거리를 구하는 방법은 각 색깔별로 w_cnt, b_cnt를 따로따로 선언하지 않고 cnt 변수 하나만 선언해서 색깔 별로 조건문을 다르게 주어 현재 들어온 색을 기준으로 cnt를 세고 return하는 방법으로 진행했다. 이 방법까지 캐치하는데 상당히 오랜 시간이 걸렸다. 어제 첫 알고리즘.. 2021. 4. 21.
[ 파이썬(python) ] 백준 4963 - 섬의 개수(BFS) 📌 백준 4963 - 섬의 개수 문제 설명 💡 나의 풀이 BFS 혹은 DFS만 잘 구현할 수 있다면 어려운 문제는 아니다. 다만, 기존 문제에서는 상, 하, 좌, 우 패턴이 등장했다면 이번에는 대각선 패턴이 등장했다. 이왕 등장했으니 다음 세 가지 패턴을 알아보자. 상, 하, 좌, 우 패턴 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] 대각선 + 상, 하, 좌, 우 패턴 dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] 대각선 패턴 dx = [-1, -1, 1, 1] dy = [-1, 1, -1, 1] 패턴2를 사용하면 쉽게 해결할 수 있다. 그리고 while문 종료조건은 입력이 0, 0이어야 하는데, 이는 if n.. 2021. 4. 20.
[ 파이썬(python) ] 백준 7576 - 토마토(BFS) 📌 백준 7576 - 토마토 문제 설명 💡 나의 풀이 나의 수준에서는 어려웠다... 익은 토마토가 1개일 경우에는 잘 구할 수 있었는데, 2개 이상인 경우는 도저히 생각이 나지 않았다. 그래서 다른사람의 코드를 조금 참고했는데 BFS를 동시에 2개를 돌리는 방법은 아예 생각도 못했고 그러다 보니까 함수의 코드도 이전에 풀던 방법과는 조금 달라서 고민하며 문제를 푸느라 반나절을 쏟아버렸다. 처음에 익은 토마토가 2개 이상 있을 때 케이스를 하나씩 더해서 두 개를 더해주면 될 줄 알았다. 컴퓨팅적으로 생각하지 않고 내키는 대로 생각해버려서 안 되는 방법으로 구현하려니까 머리가 꼬여버렸다. 그리고 문제 마지막에 모든 토마토가 익어있는 상태를 0으로 출력해야하는데, 이 경우는 제외하고 코드를 작성했다. 그래서 .. 2021. 4. 20.
[ 파이썬(python) ] 백준 1926 - 그림(BFS) 📌 백준 1926 - 그림 문제 설명 💡 나의 풀이 BFS를 이용해서 풀었는데, queue에 있는 원소를 pop할 때마다 cnt+=1해주는것을 while문에 쓰지 않고 엉뚱한 곳에 썼다가 답이 안 나와서 헤맸다. 또 중요한것은 함수가 실행될때마다 each_cnt를 1로 초기화 해주자. 아니면 값이 계속 누적된다. 그리고 최대값을 갱신해줄 때 굳이 파라미터로 넣지 않아도 return each_cnt을 해주고 나오는 값과 0부터 max로 비교해주면 나중에 제일 큰 값만 빼낼 수 있다. 가장 간단한 비교방법이니 외워두자. 외부에서 모든 좌표를 하나씩 넣을 때 BFS를 사용하는 조건이 충족되면 cnt+=1 해준다. BFS 함수 내부에서 원소를 pop할때 each_cnt+=1을 해준다. return each_cn.. 2021. 4. 20.
[ 파이썬(python) ] 백준 11724 - 연결 요소의 개수(BFS) 📌 백준 11724 - 연결 요소의 개수 문제 설명 💡 나의 풀이 이번 문제는 BFS와 DFS를 이용해서 풀었는데 시간 차이가 많이 나지 않았다.(근소하게 dfs가 48m/s정도 빨랐다.) 방향 그래프가 없을 때는 간단하게 입력값을 반대로 바꿔서 넣어주면 된다. 이후에 몇 번 노드끼리 이어졌는지를 graph에 입력하면 되는데 무 방향 그래프기때문에 순서가 바뀌어도 된다. 예제 입력1을 그림으로 표현하면 다음과 같다. 문제를 쉽게 그림으로 표현했다. graph의 index가 노드이다. from collections import deque import sys input = sys.stdin.readline def bfs(graph, start, visited): # BFS implementation queu.. 2021. 4. 19.

티스토리툴바