마이 플밍 블로그

18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 풀이 다익스트라를 이용해서 푼다. 1→P→N 순으로 가는 최단거리가 1→N 최단거리보다 작거나 같으면 SAVE HIM을 아니면 GOOD BYE를 출력한다 코드 #include #define V 5001 using namespace std; vector adj[V]; int n,e,p; int Dijkstra(int src, int nend){ vector dist(V, 100000000); dist[src] = ..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 1. 첫노드→N1 로가는 짧은경로 + N1 → N2로가는 경로 + N2에서 n번째노드로 가는 경로 2. 첫노드→N2 로가는 짧은경로 + N2 → N1로가는 경로 + N1에서 n번째노드로 가는 경로 둘중 짧은 것이 답이다. 코드 #include using namespace std; vector adj[801]; int n,e; int v1,v2; int Dijkstra(int src, int nend){ vecto..

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 다익스트라로 길을 저장하면서 풀면 된다. 코드 #include using namespace std; vector adj[1001]; int n,e; int nstart,nend; void Dijkstra(int src){ vector dist(1001, 100000002); dist[src] = 0; int path[1001]; priority_queue q; q.push(make_pair(0,src)); while(!q.em..

2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 풀이 비트연산자를 이용해서 방 구역 나누기 > 각 방 넓이 구하기 > 방 합치기 순으로 진행해서 풀었다. 코드 #include using namespace std; int board[51][51]; int room[51][51]; int roomArea[2505]; int roomNum = 1; int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; int answer = 10000000; int h,w; int maxArea..

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 풀이 이전에 했던 1600 말이 되고픈 원숭이랑 비슷하게 풀었다. 남은 벽부수기 횟수에따른 flag를 배열을 만들고 남은거리를 저장했다. 코드 #include using namespace std; int board[1001][1001]; int flag[1001][1001][11]; int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; int w,h,k; int answer = 10000000; ..

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 남은 나이트 이동 횟수에 따라 이동거리를 저장하는 배열을 만들어서 bfs로 풀었다 코드 #include using namespace std; int dhx[8] = {-2,-1,1,2,-2,-1,1,2}; int dhy[8] = {1,2,2,1,-1,-2,-2,-1}; int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; int board[201][201]; int flag[201][201][31]; int ..

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 bfs가 아닌 dfs로 풀어서 조금 애먹었던 문제이다. 섬들에 번호를 매기고 각 섬의 가장자리 부분들의 위치를 저장한뒤 가장자리 에서 부터 시작해서 다른 섬으로 다리를 점점 넓혀나가면 된다. 코드 #include using namespace std; int board[101][101]; int flag[101][101]; int region[101][101]; int regionNum = 1; int n; int dx[4] = {0,0,-1,1}; int dy[..

5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 1번 노드부터 시작해서 연결된 간선들을 탐색하며 한번 방문했으면 답에 추가하고 이미 방문했다면 연결된 간선들을 탐색만 한다. 탐색을 할때마다 카운트를 1증가시키며 카운트가 2가되면 answer을 반환한다. 코드 #include using namespace std; int n, m; int flag[501]; vector friends[501]; int Find(int u, int c){ int answer = 0; if(flag[u] == 0..