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. [백준 7576] 알고리즘 85일차 : 토마토 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net C++ BFS 토마토 농장에 갇혔다가 겨우 탈출함. 진짜. ...세상 기쁘다 문제를 설명할 기력은 없네요. 대충 토마토 빨리 익히는 게임이라고 생각하면 됩니다. 접근방법 BFS .. 과연.. 익은 토마토를 큐에 넣습니다. 다 익었는지 체크 -> 익었으면 0 출력 반복문 들어감(큐가 비어있지 않으면 계속 돌아가는 반복문) -> 큐에서 팝하고 방문했다고 체크, 인접한 토마토들 큐에 넣기 전날 큐에 .. 2021. 2. 16. [백준 2178] 알고리즘 84일차 : 미로탐색 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net C++ BFS 즐거운 미로탐색 갈수있는 길이 2차원 배열로 주어지고 0,0에서 n-1,m-1까지의 최단'거리'를 구하는 문제 경로가 아니라 인덱스를 저장할 필요는 없다 (parent배열 안갖고 있어도 된다는 소리) 접근방법 여느 BFS와 같이 큐에 인접한 노드를 저장하고 (여기서는 인접한 노드가 길이 있으며(maze배열에서 1), 아직 방문하지 않음(distances가 -1)) 동시에 인접한 노드들의 distances를 갱신하고 또 큐에서 인.. 2021. 2. 15. [백준 1012] 알고리즘 83일차 : 유기농 배추 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net C++ 유기농 배추 연휴 전날 아침부터 배추에 지렁이 심음 2차원 배열에 배추 있는 위치가 1로 표시돼있고 상하좌우로 연결된 배추들끼리 인접해 있는 것이라고 할때 인접한 배추들의 그룹 수를 구하는 문제 바로 전날 푼 2667 문제에서 빌리지수만 구하는 문제 (집 개수 필요없음) 그래서 난이도 -1 인듯 접근방법 2667문제 거의 비슷하게 풀었다. visit배열, map배열 써주고 다만 테스트케이스가 여러개라 반복문안에서 매.. 2021. 2. 10. [백준 2667] 알고리즘 82일차 : 단지번호붙이기 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net C++ DFS&BFS 이차원 배열을 그래프로 표현해서 DFS&BFS로 푸는 문제 접근방법 처음엔 이걸 인접 그래프로 만들어서 풀어야 하나 했지만 그냥 지도랑 방문여부만 배열로 만들어서 풀어도 되는 문제였다. 지도를 한칸씩 돌면서 집이 있고 & 방문하지 않은 집이 나오면 DFS에 들어간다. DFS안에서는 우선 현위치를 방문하고/cnt를 1증가하고/상하좌우를 돌면서 집이 있으면 재귀로 DFS를 들어간다/ > n;.. 2021. 2. 9. 이전 1 2 다음
