본문 바로가기

알고리즘78

2544번 - 사회망서비스(비순환 그래프) 문제: 풀이:얼리어답터가 되는 조건부터 찾아야 한다.문제에 명시되어 있는 조건은,어떤 노드가 얼리어답터가 되기 위해서는 연결된 노드가 모두 얼리어답터여야 한다는 것이다. 그렇다면 어떻게 해야 가장 적은 얼리어답터 수를 구할 수 있을까?아래 트리를 예시로 들도록 하겠다.자신 또는 바로 이웃한 노드가 얼리어답터가 되는 노드를 찾는다면, 어떤 노드가 얼리어답터가 되어야 하는지 알 수 있다.즉, 종단 노드를 찾으면, 종단노드의 이웃 노드는 반드시 얼리어답터가 되어야 한다.종단 노드가 얼리어답터가 되는 것은, 이웃 노드가 얼리어답터가 되는 것 보다 비효율적인데,종단 노드는 하나의 노드에만 연결 되어 있는 반면, 이웃 노드는 최소 2개의 노드와 연결 되어있기 때문이다.즉, 영향을 미칠 수 있는 범위가 다르다는 것이.. 2024. 10. 4.
1005번 - ACM Craft(비순환 그래프) 문제: 풀이:이 문제에서는 건물 W를 건설하는데 필요한 최소시간이라고 하지만, 최대 시간이라고 생각하는게 편하다.위의 그림에서, 4번 건물을 건설하는데 까지 걸리는 시간은 120초이다.10 + 1 + 10초를 선택해야 하는 것이 아닌, 10 + 100 + 10초를 선택해야 하기 때문에 최대 시간이라고 생각해야 한다. 위 그림은 너무 단편적이기 때문에 하나의 예시를 더 들어보겠다.원 안의 큰 숫자는 각 건물의 인덱스를 나타내고, 초록 숫자는 각 건물을 짓는데 필요한 시간을 나타낸다.예시에서 W는 7이다.1번 노드는 시작 노드이며, 3, 2번 노드로 갈 수 있다.2번 노드의 다음 노드는 4, 5번 노드이다,4번 노드까지 걸리는 시간은 10 + 20 + 5이다.5번 노드까지 걸리는 시간은 10 + 20 + 8.. 2024. 9. 29.
9470번 - Strahler 순서(비순환 그래프) 문제: 풀이:가장 큰 Strahler 순서를 구하기 위해서는, 첫 노드부터 마지막 노드까지 깊이에 따라 순차적으로 Strahler 순서를 구해야 한다.이를 위해서 각 노드는 다음 노드 정보를 저장하고 있어야 한다. 그래야 다음 노드로 이동을 할 수 있기 때문이다. 다음 노드로 이동을 했다 하더라도, 만일 이전 노드를 모두 계산하지 않고 넘어가면, 올바르게 Strahler 순서를 계산할 수 없다. 또한 문제에 조건에 따라, "들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다." 라는 조건을 고려해야 한다. 결국 마지막 노드의 Strahler 순서를 구하기 위해서는 아래 조건이 만족되어야 한다.각 노드는 다음 노드의 정보를 가지고 있어야 함각 노.. 2024. 9. 28.
16197번 - 두 동전(bfs) 문제: 풀이:최소 몇번 움직여야하는지 맞춰야 하는 문제이다.이를 dfs로 풀게되면 모든 경우의 수를 다 살펴봐야하지만, bfs로 풀면 가장 처음 목적지에 도착할때, 그 횟수를 반환해 줄 수 있다.  동전이 움직일때 꼭 고려해야 하는 사항은 두개이다.동전의 움직임을 기록하고, 중복된 위치에 동전이 있지 않게 해준다.두 동전의 지금 위치를 기록한다.1 2 두 동전의 위치를 바꿔서 기록한다.2 1 두 동전이 각 동전의 자리에 한번에 모여있는 상황을 기록한다.1, 2   두 동전이 동시에 판 밖으로 떨어지면 안된다.또한 동전은 4방향으로 움직일 수 있으니, 4방향 탐색법을 이용하면 된다. 아래 static 메서드를 이용하도록 하자.static int[][] move = {{1,0}, {-1, 0}, {0, 1}.. 2024. 9. 26.

티스토리툴바