문제 https://www.acmicpc.net/problem/6593 3차원 개념을 활용해서 푸는거라 문제 이해가 처음에는 좀 어려웠지만 문제는 쉬운 편. 풀이 입력을 받을 때, S와 E의 좌표를 저장해준다. 시작 좌표는 탐색 시작을 위해 사용한다. 목표 좌표는 출력에 사용한다. 이번 문제는 2차원 배열에서 ‘면'의 개념을 추가한 3차원으로 탐색을 해야 한다. int dx[6] = {1, -1, 0, 0, 0, 0}; int dy[6] = {0, 0, -1, 1, 0, 0}; int dz[6] = {0, 0, 0, 0, 1, -1}; 최소 이동 거리 저장 및 재방문 확인을 위한 배열을 만들어 주었다. #define MAX 31 int visited[MAX][MAX][MAX]; // 최소 이동 거리 각 ..

문제 https://www.acmicpc.net/problem/10026 풀이 BFS로 풀었다. 비장애인과 적록색약의 탐색 함수를 2개 만들어서 풀었다. 다른 방법으로는 입력 배열을 2개 만드는 방법이 있다. R or G 은 1로 저장 B는 0으로 저장 이렇게 R과 G를 같은 걸로 취급하면 함수를 1개만 짜도 된다는 장점이 있다. 소스 HTML 삽입 미리보기할 수 없는 소스

문제 https://www.acmicpc.net/problem/5014 풀이 queue를 이용한 BFS로 풀어주었다. ❎ 오답 과정 66%에서 틀렸습니다. 를 11번이나 봤는데 범위 체크가 원인이었다. #define MAX 1000000 bool isVaild(long long a) { if( a > MAX || a > F || a HTML 삽입 미리보기할 수 없는 소스

문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 과정 싸이클이 형성되면 팀이 생성된다. 싸이클이 형성되는 경우 1) 첫번째 노드와 마지막 노드가 같을 경우 4 - 7 - 6 - 4 2) n번째 노드와 미지막 노드가 같을 경우 2 - 1 - 3 - 3 🚩 반드시 알아야 할 것 재방문으로 사이클 형성을 알 수 있다. 재방문 노드 이전의 노드들 (경로)은 사이클 형성 불가한 노드라는게 판정된다. 첫번째 노드를 1, 2, 3 .. 로 진행하다가 ..

문제 https://www.acmicpc.net/problem/7562 풀이 방문한 순서대로 좌표를 저장하기 위한 데이터 타입으로 pair를 가지는 queue를 선언했다. std::queue q; 🔍 knight() 처음 함수를 실행하면 (0, 0)에서 방문할 수 있는 위치들를 탐색하여 목표 지점에 왔는지 확인한다. 첫번째 이동으로 갈 수 있는 모든 위치를 queue에 저장한다. 이 때, 재방문 방지를 위해 min[x][y] == 0 이라는 조건을 달아주었다. (한번도 방문 안한 곳이라면 queue에 넣는다.) queue에는 다음 이동으로 갈 수 있는 모든 위치를 갖게 된다. 이 과정을 (N, M)까지 반복한다. (N, M)에 도달하면 바로 return 하기 때문에 최소 이동 횟수을 바로 알 수 있다. ..

문제 https://www.acmicpc.net/problem/2178 풀이 (1, 1)에서 (N, M)까지 가는 최단 거리를 구하는 문제였다. 무조건 N, M까지 도달할 수 있다는 가정이 있는 문제였다. min[x][y]에 (1, 1)에서 (x, y)위치까지 갈 수 있는 최단거리를 저장해주었다. 현재 위치가 (r, c)였을 때 한칸 씩 이동하면 이동거리는 min[r][c] + 1 가 된다. 즉, 현재 위치에서 한칸 이동한 값이 min[x][y]보다 작으면 재귀함수를 통해 목표 지점 (N, M)까지 진행하도록 짰다. //한번도 진행하지 않은 길이거나 길을 한칸 갔을 때 최단거리가 맞다면 if(min[x][y] == 0 || min[x][y] > min[r][c] + 1) { //최단 거리를 다시 기록해주..

문제 https://www.acmicpc.net/problem/2644 풀이 당연히 DFS로 풀어야 한다고 생각했는데 BFS로 푸는 사람이 더 많은 것 같다.. 촌수는 깊이 아니냐고....... 왜 BFS로 푸는게 더 좋다고 하는거지? 아는 사람 알려주기 약속~~ 촌수 관계를 담는 그래프 평소처럼 2차원 배열로 하려다가 어떤 블로그에서 이렇게 하길래 따라 해봤다. //전역 std::vector graph; //main문 graph.assign(n+1,std::vector(0, 0)); DFS bool DFS(int v) { if(v == b) return true; ++result; visited[v] = true; //연결된 노드만 탐색 for(int i=0; i HTML 삽입 미리보기할 수 없는 소스

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 X가 3가지 연산을 이용해 K가 되는 최소 연산 횟수를 구하는 문제다. X에서 x-1, x+1, x*2를 할 수 있으니 3^n의 모든 경우의 수를 싹싹 뒤져서 만드는게 맞는걸까? 아무리 생각해봐도 아닌 것 같아서 검색의 도움을 받았다. 하지만 싹싹 뒤지는게 맞았었다. 수학 공식으로 풀 수 있을거라 생각했는데 내가 검색을 잘 못한건지 못 찾았다. 최단 시간을 구..

문제 https://www.acmicpc.net/problem/1260 문제는 간단하게 DFS와 BFS를 구현하는 문제다. 당연히 DFS와 BFS의 개념을 알아야 풀 수 있다. 풀이 노드와 간선으로 이루어진 그래프를 표현하기 위해 2차원 배열을 선언해주었다. #define MAX 1001 int arr[MAX][MAX]; 입력 받은 그래프의 노드 a와 b의 연결을 아래처럼 표현해주었다. std::cin >> a >> b; arr[a][b] = arr[b][a] = true; 이미 방문한 노드를 재방문 여부를 확인할 bool 타입 배열도 선언해주었다. bool visited[MAX] = {false, }; DFS DFS는 시작 노드 (v)로부터 가장 인접한 노드를 찾는 탐색이 반복되기 때문에 재귀함수를 이..

문제 https://www.acmicpc.net/problem/5076 5076번: Web Pages Input will consist of a number of lines of HTML code, each line containing from 0 to 255 characters. The last line will contain a single # character – do not process this line. Within the text of each line will be zero or more tags. No angle bracket will www.acmicpc.net 풀이 파싱하는게 제일 어려운 문제로 괄호 문제랑 비슷하게 풀었다. text 를 예시로 들겠다. 는 스택에 넣어준다. 는 스택의..