본문 바로가기

BFS10

[백준 11437] 알고리즘 115일차 : LCA https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net C++ BFS 그래프에서 최소 공통 조상 찾는 문제이다. LCA 알고리즘은 기본틀이 있는 것 같아서 로직 힌트를 얻고 풀기 시작했다. 공책에 미리 로직 정리하고 코드 쓰면 좋은 점 : 정신적 스트레스가 적음 (?) 접근방법 필요한 자료구조 - 그래프 연결정보를 담고 있는 인접 리스트 - 노드 방문 정보를 담고 있는 배열 - bfs 큐 - 노드의 부모노드 정보를 담고있는 배열 - 노드의 깊이를.. 2021. 8. 5.
[백준 1707] 알고리즘 89일차 : 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net C++ BFS 그래프 문제 접근방법 일단 정점을 담는 두 집합이 있다고 가정하고, 처음엔 그래프를 탐색하면서 인접한 노드는 다른 집합에 넣고 마지막에 두 집합의 교집합이 공집합이 아닌지 확인해서 결과를 출력했다. 근데 이렇게 하면 우선 이 문제에서 그래프는 모든 경우 연결그래프라고 가정하고 있지 않고, 무엇보다 시간초과가 났다. 그래서 갈아엎었다 ^_^ 방문여부를 저장하는 배열에 0,-1,1을 저장.. 2021. 2. 22.
[백준 7562] 알고리즘 88일차 : 나이트의 이동 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net C++ BFS 나이트가 있는 칸, 도달하려는 칸 인덱스가 주어지고 나이트가 도달하려는 칸까지 가는 최단거리를 구하는 문제 나이트가 이동할 수 있는 칸은 위의 사진과 같다. 접근방법 나이트가 현 위치에서 갈 수 있는 칸(8개)을 인접한 노드라고 생각하고 그래프 BFS 최단거리 문제로 풀었다. 숨바꼭질 문제랑 유사하다. distances배열과 visit배열을 사용한다. 오답노트 제출전에 디버깅에서 런타임에러가 걸렸었.. 2021. 2. 19.
[백준 1697] 알고리즘 87일차 : 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net C++ BFS 수빈이가 동생이 있는 좌표까지 가는데 걸리는 최단시간을 구하는 문제이다. 수빈이는 1초에 앞,뒤,2배만큼 이동할 수 있고 최소한 몇초만에 찾는지 구하는 문제 접근방법 인접한 노드를 현위치에서 -1, +1, *2 위치로 생각하고 distances배열에 최단거리를 저장하면서 BFS 최단거리 문제로 풀었다. 오답노트 큐에 push할때 배열의 최대 범위를 넘어나서 런타임에러가 .. 2021. 2. 18.
[백준 7569] 알고리즘 86일차 : 토마토(3차원) www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net C++ BFS 토마토 농장주가 된 기분이네요. 어제에 이어 오늘도 토마토를 익혔답니다. 다음문제가 토마토인것을 보자마자 소스라치게 놀랐어요. 하지만 어제 풀었던 거니까..하면서 풀었는데 다행히 3차원으로만 늘리는 설정만 하면 되는 코드였어요. 접근방법 2차원 토마토 문제에서 3차원배열로 늘려주고, 인접 토마토 확인할 때에도 dh를 추가해서 위 아래 토마토를 확인할 수 있도록 고쳐준다. 소.. 2021. 2. 17.
반응형