개인사

[G5] 백준 11909번 배열 탈출 C++ 다익스트라

리뷰 https://www.acmicpc.net/problem/11909흠.. 골드5 수준의 문제는 아닌 것 같기는 하다. 다익스트라만 써도 풀리긴 하는데 시간이 아슬아슬했다. 전역 변수N : 배열의 한 변의 최대값을 정의할 상수 변수n : 배열의 한 변의 길이를 저장할 변수lst : 배열의 값을 입력 받기위한 2차원 배열dx, dy : 2방향 탐색을 위한 방향 배열Pos : 현재 위치, 누적 비용, 현재 높이를 정의할 구조체, 누적 비용을 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() { priority_queue pq; pq.push({ 0, 0, 0, lst[0][0] }); vector> dist(n, vector(n, 2e9)); dist[0][0] = 0; w..

[G4] 백준 15971번 두 로봇 C++ 너비 우선 탐색

리뷰 https://www.acmicpc.net/problem/15971로봇 두개가 만나 통신하기까지 이동한 거리의 합이 최소를 만들기 위한 문제 전역 변수N : 노드 관련 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수r1, r2 : 로봇 1, 2가 위치한 노드 번호를 저장할 변수v : 방문 여부를 체크할 배열Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 저장할 Edge타입 벡터 배열Pos : 현재 위치, 누적 이동 거리, 최대 간선 길이를 정의할 구조체 함수1. bfsint bfs() { queue q; q.push({ r1, 0, 0 }); v[r1] = true; while (!q.empty()) { Pos pos = q.front(); q.pop(); ..

[G5] 백준 13265번 색칠하기 C++ 너비 우선 탐색

리뷰 https://www.acmicpc.net/problem/13265DFS로 풀이하려고 했는데... 그냥 BFS로 했다, DFS를 다시 좀 연습해야겠는데 전역 변수N : 동그라미 관련 배열의 최대 크기를 정의할 상수 변수t : 테스트 케이스의 개수를 저장할 변수n : 동그라미의 개수를 저장할 변수m : 직선의 개수를 저장할 변수edges : 간선 정보를 인접리스트로 저장할 벡터 배열colors : 각 노드의 색을 저장할 배열 함수1. bfsbool bfs(int snode) { queue q; q.push({ snode, 0 }); colors[snode] = 0; while (!q.empty()) { pii cur = q.front(); q.pop(); int cn = cur.first, cc..

리뷰 https://www.acmicpc.net/problem/23563루시우가 되어 출발지부터 목적지까지의 이동하는 최단 시간을 구하는 문제 전역 변수n, m : 맵의 세로/가로 길이를 저장할 변수sx, sy, ex, ey : 출발 및 도착지의 좌표를 저장할 변수dx, dy : 4방향 탐색을 위한 방향 배열lst : 맵 정보를 정수로 파싱하여 저장할 2차원 배열Pos : 현재 위치와 누적 소요시간을 정의할 구조체, 누적 소요시간을 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() { priority_queue pq; pq.push({ sx, sy, 0 }); vector> dist(n, vector(m, 2e9)); dist[sx][sy] = 0; while (!pq.em..

리뷰 https://www.acmicpc.net/problem/162270번 노드부터 n + 1번 노드까지 이동하는 최단 시간을 구하는 문제, 모래를 씻어야 한다는 제약 조건이 추가된 최단 경로 문제이다. 전역 변수N : 최대 노드의 개수를 정의할 상수 변수n : 특수 장비의 개수, 즉 출발지와 도착지를 제외한 노드의 개수를 저장할 변수k : 포장 도로의 개수, 즉 간선의 개수를 저장할 변수Edge : 간선 정보, 이동할 노드와 가중치를 정의할 구조체edges : 간선 정보를 저장할 Edge타입 벡터 배열Pos : 이동 정보, 현재 노드와 누적 가중치, 누적 모래를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() { priority_queue..

리뷰 https://www.acmicpc.net/problem/21942차원 맵에서 출발지에서 도착지까지 사각형이 이동하는 최단 시간을 구하는 문제 전역 변수n, m : 맵의 세로/가로 길이를 저장할 변수a, b : 사각형의 세로/가로 길이를 저장할 변수k : 장애물의 개수를 저장할 변수lst : 장애물의 위치를 표기하기 위한 배열v : 방문 여부를 확인하기 위한 배열dx, dy : 4방향 탐색을 위한 방향 배열Pos : 현재 위치와 소요 시간을 정의하기 위한 구조체 함수1. bfsint bfs(int sx, int sy, int ex, int ey) { queue q; q.push({ sx, sy, 0 }); v[sx][sy] = true; while (!q.empty()) { Pos pos = ..

리뷰 https://www.acmicpc.net/problem/2412해시맵을 기반으로 너비 우선 탐색을 수행하여 정상에 오르는 최소 시간을 구하는 문제 전역 변수Y : y좌표의 최대값을 정의할 상수 변수n : 홈의 개수를 저장할 변수t : 정상의 높이를 저장할 변수v : 홈의 좌표를 저장할 2차원 해시맵d : 이동할 수 있는 범위를 저장할 배열Pos : 현재 위치 좌표와 이동 횟수를 정의할 구조체 함수1. bfsint bfs() { queue q; q.push({ 0, 0, 0 }); while (!q.empty()) { Pos pos = q.front(); q.pop(); int cx = pos.x, cy = pos.y, cc = pos.c; //cout 너비 우선 탐색을 통해 산의 정상까지..

리뷰 https://www.acmicpc.net/problem/22116(0, 0)에서 (n - 1, n - 1)좌표로 가능 경로상의 최대 경사의 최소값을 출력하는 문제  전역 변수n : 맵의 한 변의 크기를 저장할 변수ans : 정답을 저장하기 위한 변수, 초기값은 10억보다 큰 값으로 설정한다.lst : 격자 높이 정보를 저장할 2차원 배열dx, dy : 4방향 탐색을 위한 방향 배열Pos : 시뮬레이션 시 위치 정보와 최대 경사를 정의할 구조체, 경사 값을 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() { priority_queue pq; pq.push({ 0, 0, 0 }); vector> h(n, vector(n, 2e9)); h[0][0] = 0; while (..

리뷰 https://www.acmicpc.net/problem/1486이 문제는 지문을 잘 읽어야 할 것 같다. 예제 일부가 맞지 않아 고심을 좀 한 문제  전역 변수n, m : 맵의 세로/가로 길이를 저장할 변수t : 이동 가능한 높이의 최대값을 저장할 변수d : 시간 제한을 저장할 변수lst : 맵 정보를 입력 받을 2차원 배열dx, dy : 4방향 탐색을 위한 방향 배열Pos : 산을 올라갈 때 사용할 위치와 시간을 정의할 구조체, 시간을 기준으로 오름차순 정렬한다.bPos : 산에서 내려올 때 사용할 높이와 위치, 시간을 정의할 구조체, 높이를 기준으로 내림차순 정렬한다.dest : 갈 수 있는 산을 저장하기 위한 bPos타입의 벡터 함수1. govoid go() { priority_queue p..

리뷰 https://www.acmicpc.net/problem/17835큐에 요소를 삽입하는 과정에서 N크기만큼 pq에 삽입하여 시간 초과를 받았다.  전역 변수N : 도시 관련 배열의 최대 크기를 정의할 상수 변수n : 도시의 개수를 저장할 변수m : 간선의 개수를 저장할 변수k : 면접장의 개수를 저장할 변수K : 면접장이 위치한 도시의 번호를 저장할 배열Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 인접리스트로 정의할 벡터 배열P : 시뮬레이션 정보를 정의할 구조체, 거리를 기준으로 오름차순 정렬한다. 함수1. dijkstrapair dijkstra() { priority_queue pq; vector dist(n + 1, 1e11); for (int i = 0; i cv + n..