BOJ79 백준(BOJ) 13460 구슬 탈출 2(Python) BFS 문제. 18170이랑 비슷하게 두 개의 요소를 고려하는 BFS 문제였다. 거기다가 좌표를 한 번에 여러 칸 이동해야 했기 때문에 고려할 부분이 많았다. 먼저 빨간 공을 움직이는데, 움직일 자리에 파란 공이 있을 때 파란 공도 움직일 수 있다면 둘 다 움직이고, 그렇지 않다면 break한다. 이때 파란 공이 움직여서 구멍에 도착했는지 확인하고, 구멍에 도착했다면 continue한다. 만약 빨간 공이 움직일 자리에 파란 공이 없다면 계속 움직인다. 빨간 공이 구멍에 도착했다면 flag를 수정하고, 파란 공을 마저 움직인다. 이때 파란 공이 구멍에 도착했다면 continue하고, 그렇지 않다면 횟수를 출력하고 break한다. 만약 빨간 공이 구멍에 도착하지 않은 상태라면 visited에 두 공의 좌표를.. 2022. 7. 20. 백준(BOJ) 2162 선분 그룹(Python) Union-Find에 선분 교차 판정을 곁들인 문제. 각 선분이 모두 교차하는지 확인하고, 교차한다면 Union-Find를 진행하면 되는 문제. 일반적인 선분 교차 판정과는 달리 두 선분이 하나로 겹쳐지는 경우나 한 점에서 접하는 경우도 포함해야 하기 때문에 이 부분을 고려해서 선분 교차 판정을 수정해줬다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations import bisect #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n=int(input()).. 2022. 7. 19. 백준(BOJ) 2143 두 배열의 합(Python) 누적 합 & 이분 탐색 문제. 두 배열의 모든 누적 합의 값을 각각 새로운 배열에 저장하고, A의 누적 합의 값에 대해 T-값을 B의 누적 합의 값이 저장된 리스트에서 이진 탐색을 통해 찾고, 개수를 센다. 파이썬의 bisect 라이브러리를 사용하면 쉽게 구할 수 있다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations import bisect #input=sys.stdin.readline #sys.setrecursionlimit(100000000) t=int(input()) n=int(input()) A=lis.. 2022. 7. 19. 백준(BOJ) 2110 공유기 설치(Python) 이분 탐색 문제. 공유기 간의 거리를 이분 탐색의 변수로 두고, 모든 집을 탐색하며 현재 거리로 두 집 간에 공유기를 설치할 수 있는 지를 확인한다. 공유기를 설치할 수 있다면 공유기 개수를 늘린다. 탐색이 끝나고 설치할 수 있는 공유기 개수가 입력받은 공유기 개수 이상이라면 ans를 갱신하고 start를 변경한다. 그렇지 않다면 end를 변경한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n,m=map(int,input().split()) L=[] for i.. 2022. 7. 18. 백준(BOJ) 1060 좋은 수(Python) 그냥 시키는 대로 하면 되는 문제. 우선순위 큐가 태그에 있던데 그거 안 쓰고도 풀렸다. 집합 S에 속하는 수들을 정렬하고, 정렬된 리스트를 기준으로 i번째 수와 (i+1)번째 수의 차이를 구한 뒤 (i번째 수)+1과 함께 새로운 리스트에 저장한다. 이는 좋은 구간이 존재할 수 있는 구간이다. 이때 집합 S의 최솟값이 2라면 ans에 [0,1]을 추가하고, 그 외에도 구간의 길이가 1이라면 위에서 좋은 구간이 될 수 있는 리스트에 구간을 저장하지 않고 ans에 [0,구간에 해당하는 수]를 추가한다. 좋은 구간의 조건에 따르면 구간의 경계값은 같을 수 없기 때문에, 구간의 길이가 1이라면 좋은 구간의 개수가 0이라 뒤에서 탐색할 이유가 없기 때문이다. 그 후 집합 S에 속하는 수들에 대해서도 ans에 [0.. 2022. 7. 18. 백준(BOJ) 16946 벽 부수고 이동하기 4(Python) BFS 문제. 모든 칸에 대해 탐색하는데, 벽이 아닌 칸에서 BFS를 진행한다. 인접한 모든 벽이 아닌 칸의 개수를 세고, 그 모든 칸에 동일한 고유 넘버를 지정해준 뒤 딕셔너리에 그 넘버에 해당하는 칸의 개수를 저장한다(해싱). visited에서 진행할 것이기 때문에 위의 예제에서 진행하면 다음과 같은 visited가 생성될 것이다. 000 010 000 -> 203 000 040 그 후에는 다시 모든 칸을 탐색하며 벽이 있는 칸인 경우 상하좌우의 칸이 벽이 아닌 경우 고유 넘버를 모두 저장하되, 이들이 중복되지 않도록 한다. 그 후 고유 넘버에 해당하는 칸의 개수를 모두 세서 입력받은 맵의 해당하는 칸에 더해주면 된다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sy.. 2022. 7. 17. 이전 1 ··· 5 6 7 8 9 10 11 ··· 14 다음
