본문 바로가기

백준

[백준] 7662번: 이중 우선순위 큐(파이썬) https://www.acmicpc.net/problem/7662 우선순위 큐를 응용해서 푸는 문제였다.heapq를 사용하여 구현하려고 했다. import heapqt = int(input())for _ in range(t): k = int(input()) dup = [] # 공용 리스트 min_heap = [] # 최소힙 max_heap = [] # 최대힙 # k번 만큼 명령 실행 for i in range(k): cmd, num = map(str, input().split()) num = int(num) cnt = 0 flag = True # 추가 if cmd == "I": .. 더보기
[백준] 9019번: DSLR (파이썬) https://www.acmicpc.net/problem/9019 문제를 보고, 이 문제도 BFS로 풀 수 있겠다. 라고 생각하고 BFS로 풀어나갔다.시간 제한이 6초여서 모든 경우의 수를 queue에 넣어가도 괜찮을 거라고 생각했다. from collections import dequet = int(input())def bfs(a,b): queue = deque([(a,"")]) cnt = 0 visited = [False] * 10000 visited[int(a)] = True while True: length = len(queue) for _ in range(length): da, cmd = queue.popleft() .. 더보기
[백준] 14500번: 테트로미노 (파이썬) https://www.acmicpc.net/problem/14500 문제를 읽고, BFS가 먼저 생각났다.from collections import dequen,m = map(int,input().split())graph = [ list(map(int,input().split())) for _ in range(n)]#방향dx = [1, 0, -1, 0]dy = [0, -1, 0, 1]4방향을 탐색해야 하므로, 방향 리스트를 만들어 준다.result = 0for i in range(n): for j in range(m): score = search(i,j) result = max(result, score)print(result)모든 좌표에서 나올 수 있는 점수중에 가장 큰 점.. 더보기
[백준] 16928번: 뱀과 사다리 게임 (파이썬) https://www.acmicpc.net/problem/16928 BFS 문제였다.queue에 주사위를 한 번 던질 때 갈 수 있는 모든 칸을 queue에 저장하고 만약 만약 queue에 100이 들어오면 while문을 멈춘다.from collections import dequen,m = map(int,input().split())# 사다리ladder = dict()for i in range(n): x,y = map(int,input().split()) ladder[x] = y#뱀snake = dict()for i in range(m): x,y = map(int,input().split()) snake[x] = y#방문 리스트graph = [0] * 101queue = deque(.. 더보기
[백준] 5430번: AC (파이썬) https://www.acmicpc.net/problem/5430 문제를 읽고 deque으로 풀어야겠구나 라고 생각하고 풀어나갔다.R을 만났을 때 deque.reverse()로 직접 deque을 뒤집었다.from collections import dequet = int(input())for _ in range(t): try: cmd = list(input()) num = int(input()) temp = list(map(int,input().lstrip('[').rstrip(']').split(','))) queue = deque(temp) #cmd를 하나씩 실행 for i in cmd: .. 더보기
[백준] 7569번: 토마토 (파이썬) https://www.acmicpc.net/problem/7569저번 x,y축만 있던 토마토 문제에서 z축이 추가된 문제이다. #시작할 때 익은 토마토 위치 queue에 담기for i in range(h): for j in range(m): for k in range(n): if graph[i][j][k] == 1: queue.append((i,j,k))count = 0while queue: bfs() count += 1우선 시작할 때 익은 토마토의 위치를 queue에 담는다.이후 queue가 빌 때 까지 bfs를 반복한다. bfs의 코드를 살펴보겠다. def bfs(): temp = deque([]) while que.. 더보기
[백준] 11403번: 경로 찾기(파이썬) https://www.acmicpc.net/problem/11403 문제를 읽고 저번에 풀어본 플로이드-워셜 알고리즘인가? 생각했는데 그 알고리즘으로 어떻게 풀어나가야 할 지 잘 모르겠어서 일단 DFS로 생각했다.import sysinput = sys.stdin.readline# 재귀def dfs(num): for i in graph[num]: if visited[i] == 0: # 방문한 적 없다면 방문 visited[i] = 1 # 방문 체크 dfs(i)n = int(input())graph = [[] for i in range(n)]for i in range(n): nums = list(map(int,input().split())) .. 더보기
[백준] 2667번: 단지번호붙이기 (파이썬) https://www.acmicpc.net/problem/2667 일반적인 BFS문제였다.graph 입력받고 4방향으로 BFS 돌리면 된다.from collections import dequeN = int(input())graph = []result = []for _ in range(N): temp = list(input()) graph.append(temp)#방향dx = [0,-1,0,1]dy = [1,0,-1,0]def bfs(start): queue = deque([start]) graph[start[0]][start[1]] = 2 count = 1 #queue가 빌 때 까지 while queue: x,y = queue.popleft() .. 더보기

티스토리툴바