알고리즘 별 문제 정리/최단 경로 탐색 (2) 썸네일형 리스트형 [C++] 백준 11403: 경로 찾기 문제 이해- 가중치 없는 방향 그래프 G가 주어진다.- 모든 정점 (i, j)에 대하여 i에서 j로 가는 길이 있는지 없는지 구하라. - 시간 제한: 1초- 메모리 제한: 256MB - N: 정점의 개수 (1 ~ 100, 10^2)- 인접 행렬(1일경우 경로가 존재, 0일경우 경로가 없음) - N개의 줄에 걸쳐 i에서 j로 가는 경로가 있으면 1, 없으면 0을 출력하라. 문제 풀이처음에 생각한 풀이는정점 i -> j로 가는 모든 경우의 수를 DFS로 해보는 풀이였다. 인접 행렬로 주어진 그래프를 벡터 배열을 통해 표현하고 DFS를 사용하였다. 단 i에서 다시 i로 가는 경우도 고려를 해야 했기에처음 시작 정점을 방문 표시하지 않아야한다는 주의할 점이 있었다. 1. i - > j 모든 경우의 수 DFS.. [C++] 백준 1865: 웜홀 문제 이해- N개의 지점- 방향이 없는 M개의 도로- 방향이 존재하는 음의 가중치를 가진 W개의 웜홀- 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 탐색하라. - 시간 제한: 2초- 메모리 제한: 512MB TC: 테스트 케이스의 개수 (1 ~ 5)N: 지점의 수 (1 ~ 500, 10^2)M: 도로의 개수(1 ~ 2,500, 10^3)W: 웜홀의 개수(1 ~ 200, 10^2) - TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력하라. 문제 풀이음의 가중치를 가진 최단 경로 탐색이라는 점에서 '벨만-포드 알고리즘' 사용해야 함을 인지했다.문제에서 원하는 것은 시간이 줄어들면서 출발 위치로 돌아올 수 있는지(음의 사이클이 존.. 이전 1 다음
