본문 바로가기

알고리즘31

[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.
[Back Tracking] 백준 2580번 : 스도쿠 파이썬 생각하기 0인 칸에 대해서 이 칸에 스도쿠 룰에 맞는 숫자를 넣고 다음 0인 칸에 대해서 룰에 맞는 숫자를 넣는 식으로 생각을 했다. 조건이 안맞으면 바로 이전으로 가서 다시 한번 숫자를 넣어보는 식으로 생각을 했다 prunning 조건 검사 해당 0이 있는 row에 지금 들어갈 같은 수를 가진 아이가 있는지 검사 해당 0이 있는 col에 지금 들어갈 같은 수를 가진 아이가 있는지 검사 0이 속한 아홉개의 섹션 안에 지금 들어갈 같은 수를 가진 아이가 있는지 검사 위의 세가지 조건을 0자리에 들어갈 1 ~ 9까지에 대해서 검사를 하고 맞으면 recursive하게 다음으로, 틀리면 backtracking을 진행한다 9*9를 검사하지 않고 0인 것들만 보기 입력을 받을 때, 0인 칸의 row idx와 col.. 2021. 11. 6.
[Back Tracking] 백준 9663번 : NQueen - Python 파이썬 생각하기 각 row에는 하나의 퀸만 있고 각 col에는 하나의 퀸만 있어야 한다 그리고 왼쪽 아래 대각선과 오른쪽 아래 대각선을 모두 고려해야 함 오른쪽 아래 대각선은 row idx - col idx + N -1 이 모두 같은 칸이고 왼쪽 아래 대각선은 col idx - row idx 이 모두 같은 칸이다 이를 고려하여 recursive를 돌리면 된다 처음에는 plus_mem 과 minus_mem을 리스트로 선언하여 append하였지만 이는 시간초과를 가져오는 결과를 보였다 import sys import copy input = sys.stdin.readline N = int(input()) cnt = 0 def search(row, col_mem, plus_mem, minus_mem): global c.. 2021. 11. 2.

티스토리툴바