방배동 고구마

문제 주어지는 노드사이에는 최대 1개의 도로가 있으며 양방향 도로이다. 도로에는 가중치가 있으며 노드간 이동시에는 최단 경로로 이동한다. N, 노드 수 : 5~100 M, 도로 수 : 5~5000 D, 노드 사이의 거리 이때 각 노드를 출발점으로 할때 도착 노드까지의 거리가 가장 먼 거리를 X라고 하자. 노드 중의 X가 가장 작은 X의 값을 구하라 입력 N과 M이 입력되며 노드A와 노드 B 사이의 거리 D가 아래와 같이 입력된다. 5 7 1 2 5 3 2 14 2 4 5 1 3 10 4 3 15 5 4 15 3 5 8 출력 15 입력을 그래프로 표현하면 위와 같다. 접근방식 서로 다른 가중치가 있는 맵이므로 BFS로 접근이 유효하다. BFS는 크게 2가지 종류가 있는데, 가중치가 서로 다른 경우와 가중치..

문제 주어진 지도에서 1구역, 2구역이 주어진다. 1구역에서 2구역으로 상하좌우 한칸씩 이동할 수 있다. 1구역에서 2구역으로 갈 수 있는 최단 거리를 구하라. 입력 N은 행, M은 열이며 map이 0과 1로 구분되어 입력된다. 0은 이동경로이며 1은 구역을 의미한다. 6 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 출력 4 접근방법1 1. map 전체를 탐색하여 1구역을 DFS로 확산하며 좌표를 저장한다..

문제 N*N 크기의 map이 있음 Input으로 map 크기에 맞는 cost가 들어옴 (0,0) 부터 (N-1,N-1) 까지 가는 최소비용을 구하라 입력 N은 2이상 100이하의 자연수이다. 3 041 253 620 Output 8 문제해결 더보기 DFS는 모든 경우의 수이다. 시간복잡도가 오래걸릴 수 있다.BFS를 이용하여 최소의 경우를 구할 수 있다. 단 중복방문을 무조건 허용하지 않고 이전 비용보다 좋을때 허용할 수 있도록 한다. DFS로 최초 풀이해보았으나 N이 커지면 Timeout이 났다. 모든 경우의 수이기때문에 시간복잡도가 매우 높을 것이다. #include int N; char map[100+10][100+10]; int visit[100+10][100+10]; int dx[4] = {1,..