본문 바로가기

알고리즘&자료구조65

백준 2178 1. 문제 이해 이 문제는 BFS를 응용해서 풀 수 있다. 시작지점부터 인접한 곳으로 이동할 때마다 거리를 1씩 증가시키면 된다. 연결된 칸들을 모두 방문한 경우 각 끝지점에서 시작지점을 빼면 시작지점으로 부터 몇 칸 이동했는지 알 수 있다. 이걸 이용해서 (1,1) ~ (N,M) 까지의 거리를 구할 수 있다. 2. 코드 #include #include #include using namespace std; #define X first #define Y second // 상하좌우 네 방향을 고정 // (1,0) : 우, (0,1) : 상, (-1,0) : 좌, (0,-1) : 하 int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; // 배열의 크기를 문제와 딱 맞게.. 2024. 4. 18.
BFS(Breadth First Search) 1. BFS 설명 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 원래 BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이지만 그래프 자료구조를 알아야 되기 때문에 다차원 배열에서의 BFS를 예시로 설명함 1. 시작하는 지점을 방문했다는 표시를 남기고 큐에 넣음 2. 큐에 있는 front를 pop하고 pop한 원소의 상하좌우 칸을 확인 -> 파란색이면서 아직 방문하지 않은 칸이 있으면 방문했다는 표시를 남기고 큐에 넣음 3. 2번을 계속해서 실행하다가 큐가 비어(front 할 것이 없음)있다면 BFS 알고리즘 종료 BFS의 시간복잡도는 방문했다는 표시를 남기기 때문에 모든 칸은 큐에 1번씩만 들어가게 되고 칸이 N개일 때 O(N)이 된다. 다차원 배열에서 행이 R개.. 2024. 4. 18.
백준 1021 난이도 : 중상 해결 방법 : 풀이 참고(https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x07/solutions/1021.cpp) #include #include #include using namespace std; int N, M; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; deque DQ; // 원소의 위치 for (int i = 1; i > position; while (DQ.front() != position) { // front에 뽑아내려고 하는 원소의 위치가 없는 경우 // 2번과 3번에서 어떤 연산을 수행하는게 더 최솟값을 구할수 있는.. 2024. 4. 11.
백준 15657 #include #include using namespace std; int N, M; int temp[8]; // 출력용도(N개의 값이 있는 위치를 인덱스로 저장) int arr[8]; // N개의 값 저장 bool state[8][8]; // N개의 상태(중복 허용) void func(int k) { if (k == M) { for (int i = 0; i > M; for (int i = 0; i > arr[i]; } sort(arr, arr + N); // 수열은 사전순 정렬이므로 오름차순 정렬 func(0); return 0; } 2024. 3. 17.

티스토리툴바