코딩성장스토리

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net BFS로 풀면 그게 곧 최소 거리이므로 목적지 도달할 떄 탈출하면 된다. #include #include #include #include using namespace std; typedef pair pii; int arr[301][301]; bool check[301][301]; int dx[] = { 1,2,-1,-2,1,2,-1,-2 }; int dy[] = { 2,1,2,1,-2,-1,-2,-..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제는 BFS로 풀었다. 범위가 10만이고 모든 범위를 다돌아도 시간복잡도는 O(N)이 나오므로 모든 범위에 있는 위치값을 최소 몇번인지 정해도 문제 없다. 그래서 시작 위치에서 갈 수 있는 세가지 위치 현재위치 -1,현재위치+1,현재위치*2(순간이동) 을 큐에 넣으며 탐색을 하면 된다. 코드를 보자. #include #include using namespace st..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 이 문제는 이분탐색과 bfs를 쓰면서 풀었다. 이 문제를 보고 처음 든 생각은 시간복잡도 이다. BFS와 이분탐색이 합쳐져 있기 떄문이다. BFS 시간 복잡도는 O(N) 이고 이분탐색은 O(logn) 즉 합쳐서 O(nlogn)이다. 일단 가중치(무게)를 1부터 최대값을 범위를 지정하고 무게에 따라 이분탐색을 실시했다. 섬이 연결되어 있는 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이 문제는 BFS,DFS 또는 유니온 파인드로 풀 수있다. 그래서 두 가지 풀이로 풀것이다 BFS와 유니온파인드이다. 유니온 파인드로 풀 수있는 이유는 바이러스 감염여부이고 이 그래프가 어떤 노드가 어떤 노드를 연결하고 있고는 중요하지 않고 같은 그래프인지 아닌지만 파악하면 되기 때문이다. 그래서 유니온 파인드로 풀어봤다. 그냥 간단하게 연결 된 쌍을 다 유니온 파인드 해버리면 결국 쌍이 이루어지는것들..