본문 바로가기

분류 전체보기107

[BFS] 백준 12886번 : 돌 그룹 - 파이썬 Python (보충예정) 생각하기 돌 그룹이 모두 같은 개수가 있는지를 찾는 문제이기 때문에 DFS 와 BFS 중 고민했다. 최소를 구하는 문제는 아니지만 그룹의 개수가 같아지면 바로 프로그램을 종료하면 된다고 생각했다 만약 DFS를 사용한다면 그게 그룹의 개수가 절대 같아지지 않는 경로를 탄다면 굉장히 오버헤드가 커질 것이라 생각했다 BFS로 A, B, C 조합의 주변부터 검사를 했을 때, 그룹의 개수가 같아지는 상황이 걸리면 바로 종료하기로 했다 구현하기 큐를 만들어서 해당 조합이 같지 않고 개수가 달라서 로직이 실행되고 검사시, 문제가 없다면 큐에 넣어주어서 BFS를 구현한다 visited 배열 만약 조합이 이전에 했던 조합이 또 나오면 결국 그 안에서 반복되어 무한루프가 생기기 때문에 visited 여부를 체크해가며 BF.. 2021. 11. 18.
[BFS] 백준 14502번 : 연구소 - 파이썬 Python 생각하기 처음에는 어떻게 벽 3개를 놓으면 하면 바이러스의(2번의) 확산을 적게할 수 있을까에 대해서 생각했다 하지만 고려해야할 변수가 너무 많았다. 벽이 놓였을 때, 어떤 기준으로 해당 자리에 있을 때, 확산이 최소가 되는지 벽이 한개도 아니다 세개인데 한개가 맞으면 다른 두개는 어떻게 판단할건지 코드가 복잡해지면 다시 생각하자.. 다시 생각하는게 좋았다 만약 벽 3개를 N x M 개의 좌표의 각 칸을 대상으로 3개를 뽑는 조합을 구성한다면 M이 최대가 8이므로 64 x 63 x 62가 되겠다 해당 조합을 기준으로 각각의 바이러스들을 BFS로 하여서 모든 조합 벽배치 조합을 검사하는 방식으로 진행을 하여도 64 x 63 x 62 x 64 < 1억 이므로 충분히 시간안에 해결이 가능하다 구현하기 iter.. 2021. 11. 17.
[BFS] 백준 16928번 : 뱀과 사다리 게임 - 파이썬 Python 생각하기 최소의 횟수로 주사위를 던지기 위해서는 BFS 알고리즘이 딱이었다. 가장 근처에 있는 아이들을 먼저 검사하면서 100에 딱 갔을때 바로 종료시켜버리면 그 때가 최소 주사위 던진 횟수일 것이다 잠시 BFS에 대해 정리하기 큐를 이용하여 한 정점에서 시작해서 모든 정점을 방문하는 알고리즘 단계별로 주변 노드들을 넣어가며 진행하기 때문에 최단거리 알고리즘에 적합 어떤 문제가 그래프로 변환이 가능하고 모든 가중치가 1인 경우에는 BFS로 간주 큐에 넣을 때 해당 노드 방문 표시하는 것이 중요!! 시작 정점 큐에 넣어주기 큐에 요소가 존재하는 한 무한반복하는 while문 안에서 큐의 요소를 하나 뺀다 큐에 연결된 요소들중 방문하지 않은 항목들을 다시 큐에 넣음 구현하기 뱀과 사다리가 규칙상으로는 다르지만.. 2021. 11. 13.
[Greedy] 백준 1339 : 단어수학 - 파이썬 Python 생각하기 N개의 단어가 주어졌을 때 가장 큰 자리수를 가진 알파벳에 가장 큰수를 순서대로 주면 될거 같다고 생각했다 가중치가 있으면 좋다고 생각을 했다 각 자리수에 따라 10단위의 가중치를 주기로 했다 5번째 자리 : 10000 4번째 자리 : 1000 3번째 자리 : 100 2번째 자리 : 10 1번째 자리 : 1 각각의 알파벳의 자리수 위치에 따라 각 자리수에 해당하는 가중치를 더한다. 구현하기 가중치를 더할 때, 알파벳 딕셔너리에 넣기위해 인덱스(숫자)화 해야 했다 물론 그냥 문자 그대로 딕셔너리에 넣어도 되지만 접근을 쉽게 하기 위해 숫자화 해주었다 ord('A') : 'A' character를 ascill코드로 바꾸어 준다 alpha_score 이라는 딕셔너리에 각 알파벳에 대한 가중치 값을 지.. 2021. 11. 12.

티스토리툴바