BFS (8) 썸네일형 리스트형 백준 1525 - 퍼즐 https://www.acmicpc.net/problem/1525 힌트 더보기 필요한 것: string 가능한 경우의 수: 9! 풀이 더보기 한 군데가 비어있는 퍼즐을 오름차순으로 배치하는 최소 횟수를 찾는 문제다. 비어있는 위치를 9라고 하면 1 2 3 4 5 6 7 8 9 의 형태로 퍼즐을 만드는 문제로 바꿀 수 있다. 그리고 이를 일렬로 나열하면 일직선 퍼즐을 123456789로 만드는 문제로 바꿀 수 있다. 퍼즐의 각 위치에서 이동할 수 있는 곳에 에지를 연결하면서 그래프 모델링을 하자. 그러면 현재 퍼즐의 상태가 주어졌을 때 숫자가 9인 노드는 연결된 노드의 숫자와 swap 할 수 있다는 의미가 된다. 123456789를 기준으로 9는 6, 8과 swap이 가능하다. 즉 9가 위치한 노드와 연결.. [COCI] 백준 3055 - 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제를 잘 이해해야 한다. 이동과 범람이 동시에 일어난다고 되어있다. 주어진 조건대로 이동을 잘 시뮬레이션하기 위해서는 이동을 먼저 한 다음 범람을 일으켜야 한다. 이 순서로 BFS를 진행해서 이동한 위치에 범람이 될 예정인지 아닌지는 신경쓰지 않고 큐에 넣는다. 그다음 범람을 수행한다. 그렇게 이동이 1회 끝난 뒤 다음 큐에서 꺼낼 때 범람된 상태면 해당 노드를 탈락시키고 다음 노드를 꺼내서 확인하면 된다... [KOI] 백준 2583 - 영역 구하기 https://www.acmicpc.net/problem/2583 힌트 더보기 좌표로 인해 블록 색칠에 어려움을 겪고 있다면 예제에서 제시된 좌표에서 같은 행, 같은 열끼리 이은 선분의 길이를 살펴보자. 무언가 알 수 있을지도 모른다. 풀이 더보기 이 문제는 윈도우 좌표계가 아닌 직교 좌표계에서 격자의 중앙이 아닌 모서리의 좌표가 주어진다. 일단 우리가 쉽게 접하는 윈도우 좌표계로 먼저 좌표를 바꿔주자. (M - Y좌표) 를 계산해주면 우리가 원하는 행을 구할 수 있다. 그리고 윈도우 좌표계에서는 X와 Y랑 반대가 되니 이 둘을 스왑해서 R, C 좌표로 만들어주자. 저렇게 좌표를 바꾸고 난 뒤 사각형을 채우기 용이하도록 좌측 하단 -> 우측 상단으로 주어진 좌표를 좌측 상단 -> 우측 하단으로 바꿔주도록.. 백준 16928 - 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 다른 노드로 건너뛸 수 있는 간선이 주어진다는 것과 주사위의 점만큼 움직인다는 점을 기억하며 BFS를 수행하면 된다. 전체 코드 더보기 #include using namespace std; using pii = pair; int n, m; unordered_map warp; bool visited[101]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i > go >> to; warp[go] = to; } queue q; q.push({1, 0}); visited[1] = .. 백준 7562 - 나이트의 이동 www.acmicpc.net/problem/7562 각 테스트 케이스마다 bfs를 수행하여 나이트의 최소 이동 횟수를 찾으면 된다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include using namespace std; using ll = long long; int t; int n; int a, b, c, d; int cnt; bool vst[300][300]; int n.. 이전 1 2 다음
