전체 글91 백준(BOJ) 9328 열쇠(Python) BFS 문제. 고려해줄 게 많아서 좀 귀찮았다. 먼저 맵을 확장시켜줬다. 시작을 건물 밖에서 하거니와 건물의 어떤 방향으로도 입장할 수 있기 때문에 (w+2)*(h+2) 크기로 맵을 확장시킨 후 가장자리를 모두 '.'로 둘렀다. 코딩을 처음 시작할 때 이런저런 문제를 풀면서 이미 해봤던 방법이라 쉽게 떠올릴 수 있었다. 그 후에는 현재 가진 키를 통해 갈 수 있는 문을 체크하는 배열을 만들고, BFS를 진행했다. 이미 지나온 오브젝트는 모두 '.'으로 만들어주고, 만약 열쇠를 주운 경우에는 visited와 queue를 초기화해줬다. 왜냐하면, 열쇠를 새로 줍는 순간 기존에는 갈 수 없었던 곳을 갈 수 있게 되어 이미 지나왔던 곳을 모두 다시 가봐야하기 때문이다. 코드는 다음과 같다. # -*- codin.. 2022. 7. 15. 백준(BOJ) 2342 Dance Dance Revolution(Python) DP 문제. 처음에는 2차원으로 생각해서 풀려고 했는데 안 돼서 3차원으로 풀었다. 각 시행마다 오른발, 왼발이 놓인 위치를 DP로 구현했다. 5*5*100000이라 꽤 여유있었다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) L=list(map(int,input().split())) INF=10e9 dp=[[[INF for k in range(5)] for j in range(5)] for i in range(len(L))] check={1:3,2:4,3:1,4.. 2022. 7. 14. 백준(BOJ) 1881 공 바꾸기(Python) 그리디 문제. 뽑은 카드에 적힌 숫자의 공이 박스에 들어있다면 pass, 그렇지 않다면 박스에 공을 넣어야 하는데, 빈 박스가 존재한다면 바로 박스에 넣었다고 공의 상태를 갱신하고, 없다면 현재 박스에 있는 공 중 하나를 뺀 다음 넣어야 한다. 박스에 공이 들어있는 지는 단순한 0-1 리스트로 나타냈다. 교환 연산을 해야하는 경우 어떤 공을 뺄 것인지에 대해 그리디한 방식을 써야 하는데, 현재 박스에 들어있는 공 중 앞으로 카드에서 나오지 않는 공을 1순위, 가장 나중에 등장하는 공을 2순위로 두고 그 공과 교환 연산을 진행했다. 연산 횟수를 최대한 줄이기 위해서는 박스 안에 불필요한 공이 없어야 하는데, 앞으로 카드에서 나오지 않는 공은 박스 공간을 낭비하는 가장 큰 원인이기 때문에 1순위로 배정했다... 2022. 7. 14. 백준(BOJ) 11952 좀비(Python) BFS와 다익스트라를 사용한 문제. 위험한 도시를 구하기 위해 좀비에게 점령당한 도시에서 BFS를 돌리고, 그 후 1번 도시에서 다익스트라를 돌려 N번 도시로의 최소 비용을 구한다. 일반적인 다익스트라와는 달리 간선에 가중치를 두는 것이 아닌, 도착한 노드의 타입에 따라 비용을 더하는 방식으로 다익스트라를 진행했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n,m,k,s=map(int,input().split()) p,q=map(int,input().split.. 2022. 7. 14. 백준(BOJ) 13265 색칠하기(Python) BFS 문제. 아주 전형적인 BFS 문제로, visited 배열의 케이스를 0,1,2로 나눠서 진행했다. 0이면 방문하지 않음, 1, 2는 원의 색으로 설정했다. 완전 그래프라는 보장이 없기 때문에 모든 점에 대해서 BFS를 돌려줘야 한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) t=int(input()) for i in range(t): n,m=map(int,input().split()) D={i:[] for i in range(n+1)} for j in .. 2022. 7. 13. 백준(BOJ) 2170 선 긋기(Python) 스위핑 문제. 좌표를 시작점, 끝점 기준으로 오름차순 정렬한 뒤, 값을 하나씩 참고하며 현재 선분의 왼쪽 좌표값보다 현재 참고하는 선분의 왼쪽 좌표값이 크고 오른쪽 좌표값이 더 작다면 선분을 연장한다. 즉, 선분의 길이에 (현재 참고하는 선분의 왼쪽 좌표값)-(현재 선분의 왼쪽 좌표값)만큼 선분의 총 길이에 더해주고, 현재 선분의 왼쪽 좌표값을 현재 참고하는 선분의 왼쪽 좌표값으로 변경한다. 그외에는 새로운 선분이 추가되므로 현재 참고하는 선분의 왼쪽 좌표값을 현재 선분의 왼쪽 좌표값으로 변경한 뒤 선분의 길이에 (현재 참고하는 선분의 왼쪽 좌표값)-(현재 참고하는 선분의 오른쪽 좌표값)을 더한 후 현재 참고하는 선분의 오른쪽 좌표값을 현재 선분의 오른쪽 좌표값으로, 현재 참고하는 선분의 왼쪽 좌표값을 .. 2022. 7. 13. 이전 1 ··· 8 9 10 11 12 13 14 ··· 16 다음