URL : https://www.acmicpc.net/problem/10158 [ 문제 푸는 방법 ]처음엔 그림에서 처럼 개미가 경로를 따라가게 코드를 짰다. 경로를 한칸씩 따라가면 시간이 오래 걸리므로 부딪히는 바깥선을 계산했다.그런데 더 좋은 방법이 생각났다. 개미의 X, Y좌표를 분리해서 보니 재미있는 현상이 보였다. 개미가 움직이는 X좌표만 따로 떼어서 보면 개미는 X축을 왔다갔다 왕복한다.그래서 t초 후에 개미가 X축 위의 어디에 있을 지 생각하기 더 쉬워졌다. ( p + t ) / w값을 x라 하겠다. x의 의미는 개미가 p위치에서 t초동안 너비 w를 몇번 움직였는지 계산한 값이다. x값이 홀수이면, 개미는 x = w축에서 x = 0으로 가는 도중에 멈출 것이다. 반대로 x가 짝수이면, 개미는..
주소 : https://www.acmicpc.net/problem/2606 [ 너비우선탐색(BFS) VS 깊이우선탐색(DFS) ]이 문제는 너비우선탐색(이하 BFS) 또는 깊이우선탐색(이하 DFS)로 문제를 해결할 수 있다. 두 가지 탐색방법은 그래프를 탐색할 때 사용하는 알고리즘 기법이다. 여기서 그래프는 간선과 노드로 이루어진 자료구조를 말한다. 이 말은 위 문제의 그림1에 대입해 볼 수 있다. 그림 1은 그래프 자료구조 형태이다. 숫자 1, 2, 3..을 노드라고 부른다. 그리고 각 노드를 연결하는 선을 간선이라고 한다. 그럼 그래프를 탐색하는 두 가지방법(BFS, DFS)를 설명하겠다. 첫번째 BFS는 시작 노드에서 사방으로 퍼지는 형태로 탐색하는 알고리즘이다. BFS를 그림1에 적용하면 아래와 ..
[ 해결 방법 ]제목처럼 플로이드 와셜 알고리즘을 이용해서 풀면된다. 줄여서 플로이드 알고리즘은 다이나믹 프로그래밍을 이용해서 모든 노드간의 최단거리를 구하는 알고리즘이다.다이나믹 프로그래밍을 구현하기 위한 점화식은 dp[i][j] = dp[i][k] + dp[k][j] 이다.여기서 i는 시작 노드, j는 도착 노드, k는 경유할 노드이다.i노드에서 k노드를 경유해서 j노드로 가는 경로가 i노드에서 j로 바로 가는 경로보다 짧으면 위의 점화식을 적용하면 된다. 문제에서 경로정보 중에 불필요한 정보가 들어온다.3 5 1로 들어온 입력 데이터가 나중에 3 5 10으로 들어올 때도 있다. 이 것만 걸러서 플로이드 와셜 알고리즘을 작성해주면 된다.[ 코드 ]#include #define MAX 101#defin..