Algorithm/BOJ47 [BOJ]16954 - 움직이는 미로 탈출(그래프 탐색 - bfs, dfs) https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net - 좀 특이한 그래프 탐색 문제여서 기록해둔다. 미로벽이 아래 방향으로 움직이는 경우의 수를 따로 메모리를 할당해서 저장하는 것이 아니고 시간이 1초 지날 때마다 아래 방향으로 1씩 움직이는 것을 이용해서 지금 캐릭터의 있는 위치의 t초 전, t+1초 전의 위치가 벽인지를 체크하는 방식으로 짤 수 있다. 이를 배열로 표현하면 a[nx-t][ny], a[nx-t-1][ny] 가 벽인지를 .. 2021. 6. 29. BOJ 14890 - 경사로(시뮬레이션, 배열) www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net - 2차원 지도의 row column을 왔다갔다하면서 검사를 하는게 힘들어서 행, 열을 따로 1차원 배열로 만들어서 검사하는 방식은 다른 블로그에서 팁을 얻었다. - 일단 1차원 배열로 행이나 열을 가져오면 통하는 길인지를 검사하는 것이 쉬워진다. 1. 높이 차이가 나는 경우(경사로 오르막인 경우, 내리막인 경우를 따진다) - 높이가 1 차이 나야한다. - 경사로가 지도 밖으로 를 넘어가지 않는다 - 경사로가 놓이는 지점끼리는 높이 .. 2021. 4. 13. BOJ 2250 - 트리의 높이와 너비(트리 순회방식) www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net - 트리 구현과 순회 방식을 잘 알고 있어야 풀 수 있는 문제이다. - 트리의 노드를 맨 왼쪽 열부터 순서대로 읽어야 각 레벨의 너비를 알 수 있다(in-order traversal). 이는 DFS 탐색으로 구현할 수 있다. 같은 레벨의 노드들을 담는 가변벡터를 선언해서 번호가 가장 작은 왼쪽 노드와 가장 큰 오른쪽 노드 간의 너비를 구한다. #include #include #include #.. 2021. 4. 12. BOJ 11437 - LCA(Tree) www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net - 트리에서 제시된 노드 2개 간의 가장 가까운 공통 조상을 찾는 알고리즘을 LCA 알고리즘 라고 부른다. (lowest common ancestor) 딱히 이진트리가 아니므로, 가변벡터의 트리배열을 선언하고 여기에 노드들을 담는다. 해당 노드의 레벨, 부모 정보를 담을 벡터를 선언하고, 각각의 노드의 부모를 찾기 위한 bfs탐색을 위해 방문여부 체크벡터도 선언한다. - LCA 알고리즘은 생각보다 간단한데.. 2021. 4. 12. 이전 1 ··· 4 5 6 7 8 9 10 ··· 12 다음
