백준 알고리즘44 [BOJ]2644번: 촌수계산 https://www.acmicpc.net/problem/2644 한 명의 사람(노드)는 자신을 기준으로 부모 / 자식의 관계를 가질 수 있습니다. 부모는 단 한 명이고, 자식은 여러명일 수 있으니 아래와 같이 표현할 수 있습니다. int parent[105]; vector child[105]; 그래서 특정 노드를 기준으로 부모, 자식 방향으로 BFS를 돌아서 목적 노드에 도달한다면 걸린 거리만큼 촌수를 계산해주면 되고, 목적 노드에 도달하지 못하면 -1을 출력하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2644.cc 2020. 8. 22. [BOJ]10473번: 인간 대포 https://www.acmicpc.net/problem/10473 suuntree님 풀이를 참고하여 해결하였습니다. (https://suuntree.tistory.com/152) 정점의 수가 작으므로 완전 그래프처럼 생각해도 해결할 수 있습니다. 출발점을 v[0], 도착점을 v[N]이라 놓고 나머지 중간 지점들을 입력받습니다. 특정 정점 N1과 N2의 거리 중 어떤 거리를 취할 지는 아래 두 가지 중 하나를 취하면 됩니다. 1. 대포를 사용하던가 2. 그냥 걸어가던가 두 정점 사이의 거리는 피타고라스 정리를 사용했고, getDistance 라는 함수로 구했습니다. 즉, minTime = min(getDistance(n1,n2)/5 , 2 + (getDistance(n1,n2) - 50) / 5 ) 입니.. 2020. 8. 22. [BOJ]2206번: 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 기본 BFS 유형에서 '벽을 부쉈냐'라는 상태가 추가되었습니다. 벽을 부쉈냐 / 안 부쉈냐라는 상태를 0,1 비트로 표현할 수 있습니다. 즉, 같은 칸을 x,y를 방문했어도 1. 벽을 이미 한 번 부수고 이동하는 상황은 visited[0][x][y]로 표시 2. 벽을 아직 안 부수고 이동하는 상황은 visited[1][x][y]로 표시 이렇게 위 둘은 같은 좌표를 방문했어도 서로 다른 상태가 되는 것입니다. 그러므로 bfs 탐색을 할 때 벽을 부쉈냐 안 부쉈냐까지 고려해서 탐색을 해주면 됩니다. 탐색 종료시점은 벽을 부쉈든 안 부쉈든 N,M 지점에 도착하기만 하면 됩니다. https://github.com/cottory/algorithm/.. 2020. 8. 18. [BOJ]7562번: 나이트의 이동 https://www.acmicpc.net/problem/7562 기본적인 BFS 문제입니다. 나이트가 이동할 수 있는 8칸을 다음 칸 후보로 두고 탐색하면 됩니다. https://github.com/cottory/algorithm/blob/master/BOJ/BOJ7562.cc 2020. 8. 18. 이전 1 ··· 3 4 5 6 7 8 9 ··· 11 다음
