반응형 BFS32 백준 5014번 스타트링크 - C++(cpp) 풀이 1. 각 층을 그래프의 정점으로 생각한다. 2. U버튼이나 D버튼으로 이동할 수 있는 층은 가중치 1짜리 방향 간선으로 연결한다. 3. BFS를 사용해 S번 정점에서 시작해 G번 정점으로 가는 최단 거리를 구한다. 1. 각 층을 그래프의 정점으로 생각한다. 최단거리 문제이므로 그래프로 바꾸어 생각해줄 것이다. 2. U버튼이나 D버튼으로 이동할 수 있는 층은 가중치 1짜리 방향 간선으로 연결한다. 엘리베이터를 통해 이동할 수 있는 층은 방향 간선으로 연결해줄 것이다. 버튼을 1번 눌러 이동할 수 있으므로 가중치 1짜리 방향 간선으로 연결해준다. N층에서 N+U층으로 가는 방향 간선과 N-D층으로 가는 방향 간선을 추가해주면 된다. 이때 N+U와 N-D가 1이상 F이하여야 한다. 3. BFS를 사용해 S번 .. 2022. 2. 15. 백준 16234번 인구 이동 - 스위프트(Swift) 풀이 1. 인접한 두 칸의 차이가 L 이상 R이하인 곳은 간선으로 연결되어있다고 생각한다. 2. 매일 BFS로 연합을 만들고 인구 이동을 처리해준다. 3. BFS가 하나도 이루어지지 않으면 이동이 끝난 것이다. 1. 인접한 두 칸의 차이가 L이상 R이하인 곳은 간선으로 연결되어있다고 생각한다. 현재 상황을 그래프로 바꾸어줄 것이다. 각 칸을 정점으로 생각하고, 인접한 두 칸(정점)의 인구수 차이가 L 이상 R이하라면 두 정점을 연결해준다. 2. 매일 BFS로 연합을 만들고 인구 이동을 처리해준다. 인구 이동 시뮬레이션을 진행해준다. 하루가 지날 때마다 BFS로 인접한 정점들을 연합으로 만든 뒤, 인구 이동을 처리해준다. BFS 과정에서 방문한 국가들을 배열에 담아두었다가 마지막에 배열을 순회하면서 평균 인구수.. 2022. 2. 12. 백준 19538번 루머 - 스위프트(Swift) 풀이 1. 최초 유포자부터 시작해 BFS로 루머를 퍼트려나간다. 2. X번 사람이 새로 루머를 믿게 되면, X의 모든 주변인들에 대해 주변인카운트를 1 증가시켜준다. 3. 만약 주변인카운트가 주변인 수의 절반 이상이 되면 루머를 믿게 된 것이므로 큐에 넣는다(방문한다). 1. 최초 유포자부터 시작해 BFS로 루머를 퍼트려나간다. 매분 주변인에게 루머를 퍼트리는 상황은 너비우선탐색 상황과 같다. 최초 유포자들을 모두 큐에 넣은 상태로 BFS를 시작한다. 앞으로 큐에는 루머를 믿는 사람들만 넣을 것이다. 2. X번 사람이 새로 루머를 믿게 되면, X의 모든 주변인들에 대해 주변인카운트를 1 증가시켜준다. 주변인의 절반 이상이 루머를 믿을 때 루머를 믿게 되므로, 자신의 주변인 중 몇 명이 루머를 믿고 있는지를 기.. 2022. 2. 10. 백준 7569번 토마토 - 스위프트(Swift) 풀이 + 그림 설명 1. 토마토를 그래프의 정점으로 생각한다. 2. BFS로 하루가 지날 때마다 인접한 토마토들을 하나씩 익혀가는 것을 구현한다. 3. 마지막에 안 익은 토마토가 있는지 확인한다. 1. 토마토를 그래프의 정점으로 생각한다. 들어있지 않은 칸은 무시하고, 토마토들을 그래프의 정점으로 생각한다. 전체 상자를 그래프로 바꾸어줄 것이다. 2. BFS로 하루가 지날 때마다 인접한 토마토들을 하나씩 익혀가는 것을 구현한다. 빨간색은 익은 토마토이고, 초록색은 안 익은 토마토를 나타내었다. 빨간색 정점에 적힌 숫자는 첫 날로부터 며칠 후에 익었는지를 기록한 것이다. 처음부터 3개의 토마토가 익어있는 아래와 같은 상황이라고 하자. 하루가 지나 1일 째가 되면, 바로 옆에 붙어있는 초록색 토마토 3개가 추가로 아래와 같이 .. 2022. 1. 18. 백준 2178번 미로 탐색 - 스위프트(Swift) 풀이 + 그림 설명 1. 1인 칸은 그래프의 정점으로 생각한다. 2. 인접한 칸이 1이면 그 칸으로 가는 간선을 추가한다. 3. 완성된 그래프에서 정점 (1, 1)에서 (N, M)으로 가는 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS를 사용한다. 1. 1인 칸은 그래프의 정점으로 생각한다. 현재 상황을 그래프로 나타낼 수 있다. 0인 칸은 어차피 갈 수 없는 칸이므로 무시하고, 1인 칸들을 정점이라고 생각하자. 2. 인접한 칸이 1이면 그 칸으로 가는 간선을 추가한다. 인접한 칸이 1이면 해당 칸으로 이동할 수 있다. 이것을 그래프에 표현해주면 인접한 칸으로 가는 간선을 추가하는 것과 같다. 3. 완성된 그래프에서 정점 (1, 1)에서 (N, M)으로 가는 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS를.. 2022. 1. 16. 이전 1 ··· 3 4 5 6 7 다음 반응형
