본문 바로가기
반응형

전체 글1310

[Jungol] 정올 1106 장기 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=386&sca=30 Input 9 9 3 5 2 8 Output 2 아래와 같이 말을 움직이면 2번에 졸을 잡을 수 있습니다. ① 말이 움직이는 방향은 8가지 입니다. ② visited[][] 배열을 초기에 임의의 큰 수로 초기화 한 후, BFS 탐색하면서 최소 움직임으로 방문한 횟수를 저장합니다. (즉, visited[][]에는 더 적은 움직임 횟수를 재방문 허용) ③ 졸이 위치한 좌표가 ex, ey일 때, visited[ex][ey] 출력 #include const int INF = 2e9; const int MAX_NM = 100 + 5; const int dx[] = {-2, -2, -1, -.. 2021. 2. 27.
[Jungol] 정올 1462 보물섬 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=734&sca=30 Input 5 7 WLLWWWL LLLWLLL LWLWLWW LWLWLLL WLLWLWW Output 8 - 육지가 바다로 나눠져 있다면 육지간 이동은 불가능합니다. - 연결된 육지에서 최단거리로 이동하되 가장 멀리 있는 곳의 거리를 찾는 문제입니다. → BFS - 육지(L)에 해당하는 모든 지점에서 이동할 수 있는 가장 먼거리를 찾습니다. (초기화 유의) 즉, 『L』로 표시된 모든 지점을 출발점으로 BFS 탐색하며 가장 멀리 도달한 거리를 찾습니다. - 특정 위치 (x, y)에서 출발 했을 때, visited[i][j] = (i, j)에 도달하기 위한 최단 거리 BFS 탐색이 끝.. 2021. 2. 27.
[Jungol] 정올 3008 교통수단 선택하기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2281&sca=50&page=20 Input 4 6 99 2 1 2 3 1 3 4 1 4 7 2 3 3 2 4 5 3 4 2 2 3 30 10 3 200 1000 Output 3600 해당 문제는 BFS로 해결하는 문제로 중복 방문 확인을 visited[도시][남은 시간][교통수단] 3차원 배열을 이용합니다. ex) visited[x][y][z] = x 도시에 y초를 남기고 z 교통수단으로 방문 비용 → 동일한 조건으로 더 좋은 비용이 아닌한 중복 방문 허용 X - 차로 도착하는 경우에는 도착지에 렌트카 지점이 있어야 합니다. 즉, 도착지에 렌트카 지점이 있으면 렌트카 타고 왔어도 반납할 수.. 2021. 2. 27.
[BOJ] 백준 3055 탈출 출처: https://www.acmicpc.net/problem/3055 Input 3 6 D...*. .X.X.. ....S. Output 6 물이 확장되는 BFS와 고슴도치가 이동하는 BFS 각각 구현 고슴도치가 물이 찰 예정인 곳을 이동할 수 없으므로 물에 대한 BFS를 먼저 수행한 후, 고슴도치 이동에 대한 BFS 수행. #include #include #define endl "\n" #define MAX 50 using namespace std; int R, C; char map[MAX][MAX]; bool visited[MAX][MAX]; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; pair startPos, endPos; queue wa.. 2021. 2. 27.
[SWEA] 2814 최장경로 출처: [SWEA] 문제 링크 Input 2 1 0 3 2 1 2 3 2 Output #1 1 #2 3 첫번째 Case는 간선 없이 정점 한개 존재하므로, 최장 경로의 길이 = 1 두번째 Case는 [3] - [2] - [1] or [1] - [2] - [3], 최장 경로의 길이 = 3 출발 정점을 [1] ~ [N]으로 해서 연결된 모든 간선을 DFS 탐색하여 최장 경로의 길이를 구합니다. private static void DFS(int current, int cost, boolean[] visited) { visited[current] = true; // 정점 [current]와 연결된 정점 리스트 List to = adList.get(current); for(int i = 0; i < to.size.. 2021. 2. 27.
[SWEA] 1768 숫자야구게임 출처: swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4su3xKXFUDFAUf& Input 5 8975 6142 5047 1860 5419 Output #1 6 #2 8 #3 7 #4 8 #5 7 total score = 100 total query = 36 player2가 제시한 player1이 생각하는 수와 일치하는지는 0234~9876까지 완전탐색하며 확인할 수 있습니다. 하지만 그렇게 되면 일치하는지 확인하는 query 함수 호출은 최대 9876 - 0234번 필요합니다. for (int i = 123; i 2021. 2. 27.
[Jungol] 정올 3109 숫자 야구2 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2391&sca=50&page=21 [BOJ] 2503 숫자 야구 문제와 달리 비교되는 숫자가 주어지지 않습니다. [BOJ] 백준 2503 숫자 야구 출처: https://www.acmicpc.net/problem/2503 Input 4 123 1 1 356 1 0 327 2 0 489 0 1 Output 2 ▶ 완전탐색 접근 3자리의 숫자는 1~9까지의 서로 다른 숫자로 구성되어야 합니다. 따라서 123~999까지 숫.. zoosso.tistory.com ① "1234"를 query에 보내고 결과 확인 4 strike이면 게임 종료 그렇지 않다면 그 기록을 저장해 대전 기록으로 활용해야 합니.. 2021. 2. 27.
[BOJ] 백준 2503 숫자 야구 출처: https://www.acmicpc.net/problem/2503 Input 4 123 1 1 356 1 0 327 2 0 489 0 1 Output 2 ▶ 완전탐색 접근 3자리의 숫자는 1~9까지의 서로 다른 숫자로 구성되어야 합니다. 따라서 123~999까지 숫자 0을 포함하거나 동일한 숫자가 나오는 경우를 제외합니다. ex) 133, 999, 150 등 그 외의 경우) B가 제시한 숫자들과 자리 및 동일한 숫자이지 확인하여 A가 답변한 strike 개수, ball 개수 비교 (문답한 N개를 모두 만족해야 합니다.) #include #include #include #include using namespace std; typedef struct{ string number; int strikeCn.. 2021. 2. 27.
[Jungol] 정올 3031 인형정리 출처: [Jungol] 정올 3031 인형정리 Input 7 2 1 2 2 2 1 2 1 Output 2 먼저 놓여있는 인형의 종류는 2종류이고 왼쪽에서 오른쪽으로 1, 2, 2, 2, 1, 2, 1로 7개의 인형이 진열되어 있다. 같은 종류끼리 정렬하는데 꺼낸 인형의 개수를 최소화하려면 왼쪽에서 1 번째와 6 번째 인형을 꺼내 왼쪽에서 1 번째로 유형 2의 인형을 왼쪽에서 6 번째로 유형 1의 인형을 배치한다. 이 때 꺼낸 인형의 개수는 2 개이다. Input 12 4 1 3 2 4 2 1 2 3 1 1 3 4 Output 7 O (M! * N) DFS 탐색을 통해서 인형 종류의 순서를 결정합니다. M 종류의 인형을 종류별로 배치하는 경우의 수 = M! ex) 1, 2, 3 → [1 2 3], [1 3.. 2021. 2. 27.
[Jungol] 정올 2217 DNA 조합 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1478&sca=3030 Input 4 GATTA TAGG ATCGA CGCAT Output 13 DNA 조각은 2 ≤ N ≤ 7개가 있고 각 조각의 길이는 1 ≤ L ≤ 7이다. N개의 DNA조각을 임의의 순서로 나열해 인접한 두 DNA 조각에서 앞쪽 조각의 오른쪽 끝부분이 뒤쪽 조각의 왼쪽 끝부분과 최대한 많이 일치하는 부분을 찾고, 중복되는 부분을 제거한 후 나머지 부분을 순서대로 모아 새로운 DNA 조합을 만든다. 예를들어 GATTA + TACA = GATTACA DFS를 이용한 백트래킹으로 두 문자열을 연결할 때 중복되는 문자의 개수를 구합니다. DNA 조각의 개수가 최대 7개이므로 .. 2021. 2. 27.
반응형

티스토리툴바