https://programmers.co.kr
문제: n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
풀이: 현재 위치를 i 라고 하자.
이때까지 방문을 한적이 없고, i와의 거리가 1차이나는 노드를 배열에 저장한 후 visit을 true로 바꿔준다.
https://www.acmicpc.net/problem/1697
풀이: 현재 위치를 x라고 할 때, x + 1, x - 1, x * 2 위치를 BFS 를 통해 하나씩 찾아간다.
동생의 위치와 같아진다면 몇번 이동했는지 출력한다.
x + 1 은 동생의 위치보다 커질 필요가없으므로 동생의 위치보다 작을때만 이동한다. x * 2 는 동생의 위치 + 1 보다 크다면 (x - 2) * 2 를 하는 것이 이득이므로 제외한다. 현재 위치는 0보다 작아질 수 없으므로 제외한다. 이미 한번 방문한 위치는 다시 방문할 필요없으므로 제외시킨다.
비트연산자
비트연산자 DP문제를 푸는데 있어, 연산속도를 빠르게 하기 위해 사용 « , » 시프트 연산자. 비트의 자리를 옮겨줌 ex)
1 « 3
1000
NOT - ( ~ ) 0 은 1로 1은 0으로 반대로 바꿔준다. ex)
0000000
1111111
AND - ( & ) 둘 다 1 일때만 1, 아니면 0 ex)
1100110
& 1011001
1000110
OR - ( | ) 둘 중 하나라도 1이라면 1, 아니면 0 ex)
