Category: Programming

0

백준 1753 - 최단 경로

https://www.acmicpc.net/problem/1753 문제 해설가장 기본적이고 정형화된 다익스트라 문제이다! 다익스트라 알고리즘에서는 우선순위 큐를 사용하는데 기본적으로 우선순위 큐는 값이 큰 것부터 우선적으로 나가게 된다. #include <bits/stdc++.h>using namespace std;#define INF 987654321int V, E;int startPoint;int dist[20002]; // dist[x] : 시작점으로부터 점 x까지의 최단 거리를 저장한다.vector<vector<pair<int, int>>> graph;void dijkstra(int start) { // 초기값은 무한대로 설정해 놓는다. for (int i = 1; i < V + 1; i++) { dist[i] = INF; } priority_queue<pair<int, int>> pq; pq.push({0, start}); dist[start] = 0; while (!pq.empty()) { int cntDist = -pq.top().first; int cntVertex = pq.top().second; pq.pop(); // 현재 점까지의 거리와 저장된 최단거리를 비교한다. // 현재 점까지의 거리가 더 큰 경우는 나중에 최단거리가 갱신된 것이다. // 우리는 각 점에 최단거리로 간 상태에 대해서만 갱신을 진행하므로 밑의 연산은 진행하지 않는다. if (cntDist > dist[cntVertex]) { continue; } // 아래 로직을 대신 사용해도 결과는 똑같이 나온다. // 즉 현재 점까지의 거리가 최단거리까지와 일치하는지 확인하는 단계이다. // if (cntDist != dist[cntVertex]) { // continue; // } for (int i = 0; i < graph[cntVertex].size(); i++) { int nextVertex = graph[cntVertex][i].first; int weight = graph[cntVertex][i].second; // cntDist 대신 dist[cntVertex]를 사용해도 결과는 동일하다 // int nextDist = dist[cntVertex] + weight; int nextDist = cntDist + weight; if (dist[nextVertex] > nextDist) { dist[nextVertex] = nextDist; // 값을 음수로 저장해 우선순위가 반대가 되도록 한다. pq.push({-nextDist, nextVertex}); } } }}int main(void) { cin >> V >> E; cin >> startPoint; graph = vector<vector<pair<int, int>>>(V + 1); for (int i = 0; i < E; i++) { int a, b, weight; cin >> a >> b >> weight; graph[a].push_back({b, weight}); } dijkstra(startPoint); for (int i = 1; i <= V; i++) { if (dist[i] == INF) { cout << "INF" << '\n'; } else { cout << dist[i] << '\n'; } } return 0;} priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 우선순위 큐에 greater<pair<int, int>>> pq 정렬 방식을 통해 값이 작은 것부터 우선적으로 나가게 된다. #include <iostream>#include <vector>#include <queue>using namespace std;#define INF 2000000000// 정점의 개수 : v, 간선의 개수 : eint v, e;vector<vector<pair<int, int>>> graph;vector<int> dist;vector<bool> check;int start_node;void dijkstra(){ for (int i = 1; i <= v; i++) dist[i] = INF; dist[start_node] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, start_node}); while (!pq.empty()) { int weight = pq.top().first; int cnt_node = pq.top().second; pq.pop(); if (check[cnt_node] == true) continue; check[cnt_node] = true; // 점 cnt_node에 연결된 간선의 개수 int edge_num = graph[cnt_node].size(); for (int j = 0; j < edge_num; j++) { // from : 현재 위치, to : 다음 위치, from_to_weight : 현재위치에서 다음위치 까지의 가중치 int from = cnt_node, to = graph[cnt_node][j].first, from_to_weight = graph[cnt_node][j].second; if (dist[to] > dist[from] + from_to_weight) { dist[to] = dist[from] + from_to_weight; pq.push({dist[to], to}); } } }}int main(void){ scanf("%d %d %d", &v, &e, &start_node); dist = vector<int>(v + 1, INF); check = vector<bool>(v + 1, false); graph = vector<vector<pair<int, int>>>(v + 1); for (int i = 0; i < e; i++) { int from, to, weight; scanf("%d %d %d", &from, &to, &weight); graph[from].push_back({to, weight}); } dijkstra(); for (int i = 1; i <= v; i++) { if (dist[i] == INF) printf("INF\n"); else { printf("%d\n", dist[i]); } } return 0;}

0

JPA 란?

JPA 란?객체를 이용해 DataBase 테이블을 다루기 위해 만들어진 ORM(Object Relation Mapping) 기술

0

백준 1726 - 로봇

링크https://www.acmicpc.net/problem/1726 채점 현황 전체 소스 코드#include <iostream>#include <queue>using namespace std;int M, N;int map[101][101];bool check[101][101][4];int dx[4] = {0, 1, -1, 0};int dy[4] = {-1, 0, 0, 1};// char dir[4] = { 'N', 'E', 'W', 'S' };struct point { int y; int x; int dir;};int main(void) { cin >> M >> N; for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { cin >> map[i][j]; } } point start, goal; int tempY, tempX, tempD; cin >> tempY >> tempX >> tempD; start.y = tempY; start.x = tempX; start.dir = tempD % 4; cin >> tempY >> tempX >> tempD; goal.y = tempY; goal.x = tempX; goal.dir = tempD % 4; queue<point> q; q.push(start); check[start.y][start.x][start.dir] = true; int num = 0; while (!q.empty()) { int q_size = q.size(); while (q_size--) { int y = q.front().y; int x = q.front().x; int d = q.front().dir; q.pop(); if (y == goal.y && x == goal.x && d == goal.dir) { cout << num << '\n'; return 0; } int nextR, nextL; if (d == 0) { nextR = 1; nextL = 2; } else if (d == 1) { nextR = 3; nextL = 0; } else if (d == 2) { nextR = 0; nextL = 3; } else if (d == 3) { nextR = 2; nextL = 1; } if (check[y][x][nextR] == false) { check[y][x][nextR] = true; q.push({y, x, nextR}); } if (check[y][x][nextL] == false) { check[y][x][nextL] = true; q.push({y, x, nextL}); } for (int i = 1; i <= 3; i++) { int nx = x + dx[d] * i; int ny = y + dy[d] * i; if (1 <= ny && ny <= M && 1 <= nx && nx <= N) { if (map[ny][nx] == 1) { break; } if (check[ny][nx][d] == false) { check[ny][nx][d] = true; q.push({ny, nx, d}); } } } } num++; // for (int i = 1; i <= M; i++) { // for (int j = 1; j <= N; j++) { // cout << check[i][j][3] << " "; // } // cout << endl; // } // cout << endl; }}

0

1707 이분 그래프

링크https://www.acmicpc.net/problem/1707 채점 현황 전체 소스 코드#include <iostream>#include <vector>using namespace std;int T, V, E;vector<vector<int>> arr;bool check[20002];bool colorCheck[20002];int color[20002];void paintColor(int cnt, int cntColor) { for (int i = 0; i < arr[cnt].size(); i++) { int next = arr[cnt][i]; if (check[next] == false) { if (cntColor == 1) { color[next] = 2; check[next] = true; paintColor(next, 2); } else { color[next] = 1; check[next] = true; paintColor(next, 1); } } }}bool confirmColor(int cnt) { bool isTrue = true; for (int i = 0; i < arr[cnt].size(); i++) { int next = arr[cnt][i]; if (color[cnt] != color[next]) { if (colorCheck[next] == false) { colorCheck[next] = true; isTrue = confirmColor(next); } } else { return false; } } return isTrue;}int main(void) { cin >> T; while (T--) { cin >> V >> E; arr = vector<vector<int>>(V + 1); for (int i = 0; i < E; i++) { int x, y; cin >> x >> y; arr[x].push_back(y); arr[y].push_back(x); } for (int i = 1; i <= V; i++) { if (check[i] == false) { check[i] = true; color[i] = 1; paintColor(i, 1); } } bool isTrue; for (int i = 1; i <= V; i++) { if (colorCheck[i] == false) { colorCheck[i] = true; isTrue = confirmColor(i); if (isTrue == false) { cout << "NO" << '\n'; break; } } } if (isTrue == true) { cout << "YES" << '\n'; } for (int i = 1; i <= V; i++) { check[i] = 0; colorCheck[i] = false; color[i] = 0; } }}

0

백준 1600 - 말이 되고픈 원숭이

링크https://www.acmicpc.net/problem/1600 체점 현황 문제 풀이 말처럼 뛸 수 있는 횟수(k), width, height를 입력 받는다. field에 대한 정보를 입력 받는다. (0, 0)에서 시작해 (width-1, height-1)까지 갈 수 있는 최소 횟수를 탐색한다. 원숭이가 움직일 수 있는 방법은 두가지가 존재한다. 말처럼 뛸 수 있는 방법(k내의 횟수에서) 상하좌우로 움직일 수 있는 방법 말이 (width-1, height-1)에 도착하면 그 횟수를 반환한다. 만약 도착하지 못할 경우 -1을 반환한다. 말이 움직인 횟수를 출력해준다. 전체 소스 코드#include <bits/stdc++.h>using namespace std;int numOfKnight;int width, height;int field[202][202];bool check[31][202][202];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};int horse_dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};int horse_dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};struct point { int k; int y; int x;};int bfs(int y, int x) { check[0][y][x] = true; queue<point> q; q.push({0, y, x}); int count = 0; while (!q.empty()) { int q_size = q.size(); while (q_size--) { int cntK = q.front().k; int cntY = q.front().y; int cntX = q.front().x; q.pop(); if (cntY == height - 1 && cntX == width - 1) { return count; } if (cntK < numOfKnight) { for (int i = 0; i < 8; i++) { int ny = cntY + horse_dy[i]; int nx = cntX + horse_dx[i]; if (0 > ny || ny >= height || 0 > nx || nx >= width) continue; if (field[ny][nx] == 0 && check[cntK + 1][ny][nx] == false) { check[cntK + 1][ny][nx] = true; q.push({cntK + 1, ny, nx}); } } } for (int i = 0; i < 4; i++) { int ny = cntY + dy[i]; int nx = cntX + dx[i]; if (0 > ny || ny >= height || 0 > nx || nx >= width) continue; if (field[ny][nx] == 0 && check[cntK][ny][nx] == false) { check[cntK][ny][nx] = true; q.push({cntK, ny, nx}); } } } count++; } return -1;}int main(void) { cin >> numOfKnight >> width >> height; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { cin >> field[i][j]; } } int minValueOfMove = bfs(0, 0); cout << minValueOfMove << '\n'; return 0;}

0

백준 1260 - DFS와 BFS

링크https://www.acmicpc.net/problem/1260 문제 풀이그래프탐색에 있어 가장 기본적인 DFS, BFS를 사용해볼 수 있는 유형이다. 좌표 자체가 존재하지 않아 1차원적인 check방식을 통해 탐색해 나간다. cpp 코드#include <bits/stdc++.h>using namespace std;// 점점의 개수 : N, 간산의 개수 M, 탐색을 시작할 정점의 번호 Vint N, M, V;bool check_dfs[1010];bool check_bfs[1010];int graph[1010][1010];void bfs(int start) { queue<int> q; q.push(start); check_bfs[start] = true; while (!q.empty()) { int cnt = q.front(); q.pop(); cout << cnt << ' '; for (int i = 1; i <= N; i++) { if (graph[cnt][i] == 1 && check_bfs[i] == false) { check_bfs[i] = true; q.push(i); } } }}void dfs(int depth, int cnt) { check_dfs[cnt] = true; if (N <= depth) { return; } cout << cnt << ' '; for (int i = 1; i <= N; i++) { if (graph[cnt][i] == 1 && check_dfs[i] == false) { dfs(depth + 1, i); } }}int main(void) { cin >> N >> M >> V; for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; graph[a][b] = 1; graph[b][a] = 1; } dfs(0, V); cout << '\n'; bfs(V); return 0;} java 코드import java.io.IOException;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Main { static int n, m, v; static int map[][]; static boolean bfs_check[]; static boolean dfs_check[]; public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); v = sc.nextInt(); map = new int[n + 1][n + 1]; for (int i = 0; i < m; i++) { int from, to; from = sc.nextInt(); to = sc.nextInt(); map[from][to] = 1; map[to][from] = 1; } bfs_check = new boolean[n + 1]; dfs_check = new boolean[n + 1]; dfs(v); System.out.println(); bfs(v); sc.close(); } static void dfs(int node) { System.out.print(Integer.toString(node) + ' '); dfs_check[node] = true; for (int i = 1; i <= n; i++) { if (map[node][i] == 1 && dfs_check[i] == false) { dfs(i); } } } static void bfs(int start) { Queue<Integer> q = new LinkedList<Integer>(); q.offer(start); bfs_check[start] = true; System.out.print(Integer.toString(start) + ' '); while (!q.isEmpty()) { int cnt = q.remove(); for (int i = 1; i <= n; i++) { if (map[cnt][i] == 1 && bfs_check[i] == false) { bfs_check[i] = true; q.offer(i); System.out.print(Integer.toString(i) + ' '); } } } }} python 코드

0

백준 1012 - 유기농 배추

링크https://www.acmicpc.net/problem/1012 채점 현황 문제 풀이전형적인 색칠하기 유형히다.이 문제는 testcase문제이기 때문에 각 case마다 데이터를 초기화 해줘야 한다. field를 탐색하면서 배추가 심어져 있는 위치를 찾는다. 배추가 심어져 있는 곳을 찾았다면 이전에 탐색을 했는지 확인한다. 탐색한 적이 없다면 다음으로 넘어간다. 탐색한 적이 있다면 1로 돌아간다. 배추가 심어져 있는 주변에 다른 배추들이 있는지 탐색한다. 탐색횟수가 배추 흰 지렁이의 갯수가 된다. BFS를 이용한 코드