코딩성장스토리

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제는 각 섬마다 그룹화가 필요하다. 그 이유는 최단 거리를 구하기 위해서 DFS를 이용해야 하는데 그냥 돌려버리면 최단거리가 아닌 각 섬에서 출발하여 중간에서 만나는 거리가 구해지기 때문이다. 즉 섬마다 그룹을 나눈다음에 각 섬끼리의 최단거리를 각각 구해야한다. 즉 이 문제는 DFS를 각 섬의 개수만큼 돌려서 최단거리를 구하면 된다. #include #include #include using na..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제는 좌표(n,m)까지 최단 경로를 구하는 것이다. 최단 경로를 구하는 문제는 DFS보다 BFS가 훨씬 효율적이다. 방문하면 그값을 전에 값에 1씩더하면서 가면 n,m을 도달하게 되고 그 값이 즉 값이다. 그리고 다른 경로로 온다고 해도 이미 최단으로 방문되었으므로 값이 바뀔 일은 없다. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 12 13 2 10 14 15 3 9 15 4 8 16 5 ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이 문제를 풀때 일단 2차원배열로 값을 받는다음에 위치 값 x+1,y x,y+1 x-1,y x,y-1 4가지 경우를 고려해가면서 값을 구하면 되는 문제이다 그리고 탐색을 했을 경우에는 방문한것을 체크해줬다. #include #include #include #include #pragma warning(disable: 4996) using namespace std; bool check[30][30] =..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이번 문제를 풀때 생각했던 것은 사이클과 DFS 이다. 일단 사이클은 이미 방문한 지점을 다시 들르면 사이클이라 정의했었다. 나는 접근을 맨 처음 들어간 값과 마지막이 가리키는 값이 일치하면 사이클로 1개씩 추가하고 배열들을 매번 초기화 해줬다. 밑에 코드를 보자 #include #include #include #include #include #include #include #include #defin..