문제 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 삽입 미리보기할 수 없는 소스