본문 바로가기

분류 전체보기263

[백준] 1062번 - 가르침 (파이썬) # 가르침 import sys input = sys.stdin.readline N, K = map(int, input().split()) arr = [] for _ in range(N): arr.append(input().strip()) alpha = ['a', 'n', 't', 'i', 'c'] alpha_list = ['b', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'o', 'p', 'q', 'r', 's', 'u', 'v', 'w', 'x', 'y', 'z'] def choose_alpha(n, start): global result if n == 0: result = max(result, check()) return for i in range(start, .. 2022. 1. 22.
[백준] 2638번 - 치즈 (파이썬) # 치즈 import sys from collections import deque import copy input = sys.stdin.readline dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def air_check(arr): q = deque() q.append((0, 0)) arr[0][0] = 2 while q: x, y = q.popleft() for k in range(4): nx = x + dx[k] ny = y + dy[k] if 0 2022. 1. 22.
[백준] 1600번 - 말이 되고픈 원숭이 (파이썬) # 말이 되고픈 원숭이 from collections import deque import sys input = sys.stdin.readline monkey_dx = [0, 1, 0, -1] monkey_dy = [1, 0, -1, 0] horse_dx = [-2, -1, 1, 2, 2, 1, -1, -2] horse_dy = [1, 2, 2, 1, -1, -2, -2, -1] def bfs(n): q = deque() q.append((0, 0, n)) count = [[[0] * (n + 1) for _ in range(M)] for _ in range(N)] while q: x, y, K = q.popleft() if x == N-1 and y == M-1: return count[x][y][K] .. 2022. 1. 21.
[백준] 1647번 - 도시 분할 계획 (파이썬) MST, 프림 1. 값을 인접리스트로 받는다(양방향) 2. q에 초기값을 놓고(아무 노드) q가 빌때까지 - 현재 그래프에 연결이 안된 경우에만 (connected == False) - 연결을 해주고(connected == True) total에 비용(cost) append - 인접리스트를 for문으로 돌면서 연결이 안된 노드만 heapq에 heappush 3. max_value = total에서 가장 큰 값 4. 마을을 두곳으로 나눠야 해서 가장 비용이 큰 max_value를 sum(total)에서 빼준다. MST문제이며 크루스칼알고리즘으로도 풀 수 있다. 프림알고리즘으로 풀었다. 2022. 1. 21.
[백준] 12581번 - 숨바꼭질 2 (파이썬) # 숨바꼭질 2 from collections import deque def bfs(start): global result q = deque() q.append(start) arr[start] = 0 while q: x = q.popleft() if x == K: result += 1 continue for nx in (x*2, x+1, x-1): # 최소시간이 arr[K]에 이미 있는 경우에는 같을 때도 # q.append해서 result가 증가될 수 있도록 if 0 2022. 1. 21.
[백준] 17142번 - 연구소 3 (파이썬) # 연구소 3 import sys import copy from collections import deque input = sys.stdin.readline MAX = sys.maxsize dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] result = MAX def bfs(arr): global result time = [[0] * N for _ in range(N)] q = deque() for i in range(N): for j in range(N): if arr[i][j] == 'a': q.append((i, j)) time[i][j] = 1 while q: x, y = q.popleft() for k in range(4): nx = x + dx[k] ny = y + dy[k.. 2022. 1. 20.
[백준] 4485번 - 녹색 옷 입은 애가 젤다지? (파이썬) # 녹색 옷 입은 애가 젤다지? from collections import deque import sys input = sys.stdin.readline MAX = sys.maxsize dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def bfs(): q = deque() q.append((0, 0)) visit[0][0] = arr[0][0] while q: x, y = q.popleft() for k in range(4): nx = x + dx[k] ny = y + dy[k] if 0 2022. 1. 20.

티스토리툴바