개인사

[G4] 백준 22865번 가장 먼 곳 C++ 다익스트라

리뷰 https://www.acmicpc.net/problem/22865친구들의 집으로 부터 각 땅의 최단 거리를 구하고, 친구들이 살고 있는 집으로부터 가장 먼 곳의 땅 번호를 출력하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 자취할 땅 후보의 개수를 저장할 변수m : 땅과 땅 사이를 잇는 도로의 개수를 저장할 변수a, b, c : 친구 A, B, C가 사는 위치를 저장할 변수Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 인접 리스트로 저장할 벡터 배열Pos : 현재 위치와 누적 가중치를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstravector dijkstra(int sn) { priority_queue pq; pq.push..

[G3] 백준 17182번 우주 탐사선 C++ 플로이드 와샬, 다이나믹 프로그래밍, 비트마스킹

리뷰 https://www.acmicpc.net/problem/17182플로이드 와샬로 정점간 최단 거리를 구하고 dp를 활용해 모든 행성을 탐사하는데 걸리는 최소 시간을 구하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 행성의 개수를 저장할 변수k : 탐색을 시작한 행성 번호를 저장할 변수lst : 행성간 거리를 저장할 2차원 배열dp : x개의 행성을 탐사했고, y번째 행성에 있을때의 최소 시간을 저장할 2차원 배열 함수1. dfsint dfs(int mask, int cur) { if (mask == (1 각 행성을 방문하며 모든 행성을 방문하는 최소 시간을 구하기 위한 함수 문제풀이n, m값을 입력 받고, n*n크기의 인접 행렬 lst에 값을 입력 받아 초기화를 진행해 ..

[P4] 백준 14868번 문명 C++ 너비 우선 탐색, 플러드 필, 유니온 파인드

리뷰 https://www.acmicpc.net/problem/14868백준 서버가 터진건지 문제 채점만 5분이 걸렸다, 첫트는 시초가 떴으나 조금 최적화 해주니 AC를 받은 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수K : 문명의 최대 개수를 정의할 상수 변수n : 세계의 한변의 크기를 저장할 변수k : 문명 발상지의 개수를 저장할 변수lst : 세계 정보를 저장할 2차원 배열Pos : 현재 위치와 문명 번호를 정의할 구조체flood : floodfill을 수행할 위치와 문명 번호를 저장할 Pos타입 큐parent : 각 문명 번호가 속한 그룹을 저장할 배열dx, dy : 4방향 탐색을 위한 방향 배열 함수1. Findint Find(int a) { if (parent[a] == a) ..

리뷰 https://www.acmicpc.net/problem/13911맥세권과 스세권을 만족하는 최단거리의 합이 최소인 집을 구하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수v : 정점의 개수를 저장할 변수e : 도로의 개수를 저장할 변수Edge : 간선 정보를 정의할 구조체edges : 인접 리스트를 저장할 Edge타입 벡터 배열Pos : 현재 정점의 번호와 누적 거리를 정의할 구조체, 누적 거리를 기준으로 오름차순 정렬한다. 함수1. dijkstravoid dijkstra(priority_queue& pq, vector& dist, int limit) { while (!pq.empty()) { Pos pos = pq.top(); pq.pop(); int cn = pos.cn, ..

리뷰 https://www.acmicpc.net/problem/93763번의 다익스트라를 수행하여 푸는 문제 아이디어가 대단한 문제인듯 하다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수t : 테스트 케이스의 개수를 저장할 변수n, m : 맵의 세로/가로 길이를 저장할 변수lst : 맵 정보를 저장할 2차원 배열bool : 방문 여부를 체크할 2차원 배열dx, dy : 4방향 탐색을 위한 방향 배열Pos : 현재 위치와 문을 연 누적 개수를 정의할 구조체, 문을 연 개수를 기준으로 오름차순 정렬한다. 함수1. dijkstravector> dijkstra(int sx, int sy) { priority_queue pq; pq.push({ sx, sy, 0 }); vector> dist(n + 2..

리뷰 중싱점 기준 w*w크기에 친구들이 가장 많은 수와 좌표를 구하는 문제, 만들어 진지 얼마 되지 않아 문제 설명이 부족하다. 전역 변수N : 배열의 최대 길이를 정의할 상수 변수n : 친구의 수를 저장할 변수수r, c : 강의실의 세로/가로 길이를 저장할 변수w : 정사각형의 범위를 저장할 변수F : 친구가 앉았는지 여부를 저장할 2차원 배열PS : 누적합을 저장할 2차원 배열 함수없음 문제풀이n, r, c, w값을 입력 받고, n명의 친구가 앉은 위치를 입력 받아 F배열에 true처리해 준다.r*c를 순회하며 PS배열에 강의실을 기준으로 2차원 누적합을 저장해 준다.변수 ans, x, y를 0으로 초기화 하고, 상수 변수 h를 w를 2로 나눈 몫을 저장해 준다.1다시 r*c크기의 맵을 순회하며 ..

리뷰 https://www.acmicpc.net/problem/33905엄이 방문할 수 있는 친구 집의 수를 출력하는 문제 전역 변수N : 배열의 최대 길이를 정의할 상수 변수n : 친구의 수를 저장할 변수m : 도로의 수를 저장할 변수k : 여행을 떠난 친구의 수를 저장할 변수v : 방문한 친구를 저장할 배열edges : 간선 정보를 인접 리스트로 저장할 벡터 배열 함수1. bfsvoid bfs() { queue q; q.push(1); v[1] = true; int cnt = 0; while (!q.empty()) { int cn = q.front(); q.pop(); for (int nn : edges[cn]) { if (v[nn]) continue; cnt++; v[nn] = tr..

리뷰 https://www.acmicpc.net/problem/2637위상 정렬을 통해 선수 조건에 따른 sum값을 갱신시키며 기본 제품까지의 값을 구하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 부품의 개수를 저장할 변수m : 간선의 개수를 저장할 변수cnts : 선수 부품의 개수를 저장할 배열sum : 필요 부품의 개수를 저장할 배열conn : 후위 부품이 있는지 여부를 저장할 배열Edge : 다음 노드와 개수를 정의할 구조체edges : 간선 정보를 인접 리스트로 저장할 벡터 배열 함수없음 문제풀이n, m값을 입력 받고, m개의 간선 정보를 입력 받아 변수 x, y, k에 부품 번호와 개수를 입력 받는다.conn[x]를 true로 저장, edges[x]에 {y, k}를 추..

리뷰 https://www.acmicpc.net/problem/16920각 라운드 마다 플레이어 번호가 낮은 순서부터 확장할 수 있을 만큼 확장 후 최종적으로 플레이어 마다 확장한 크기만큼을 출력하는 문제 전역 변수N : 맵 한변의 최대 길이를 정의할 상수 변수P : 플레이어 관련 배열의 최대 길이를 정의할 상수 변수n, m : 맵의 세로/가로 변의 길이를 저장할 변수p : 플레이어 수를 저장할 변수v : 맵의 방문 여부를 저장할 배열S : 플레이어 당 한 턴에 이동할 수 있는 거리를 저장할 배열cnt : 플레이어 당 점령한 성의 개수를 저장할 배열Pos : 시뮬레이션 시 사용할 현재 위치와 남은 이동 횟수를 정의할 구조체dx, dy : 4방향 탐색을 위한 방향 배열qs : 플레이어 별 Pos타입의 큐..

리뷰 https://www.acmicpc.net/problem/2479비트 차이가 한개 나는 노드끼리 간선을 연결하고 특정 노드에서 목표 노드로 이동 가능한 경로를 구하는 문제 전역 변수N : 배열의 최대 길이를 정의할 상수 변수n : 노드의 개수를 저장할 변수l : 노드의 비트 개수를 저장할 변수H : 노드의 비트 정보를 저장할 배열c : 어떤 노드로 부터 왔는지를 저장할 배열v : 방문 여부를 체크할 배열edges : 간선 정보를 인접 리스트로 저장할 벡터 배열 함수1. bfsvector bfs(int sn, int en) { queue q; q.push(sn); v[sn] = true; while (!q.empty()) { int cn = q.front(); q.pop(); if (cn == ..