본문 바로가기

백준

[코딩인터뷰] 백준 1987번 DFS import sys sys.setrecursionlimit(10 ** 5) # 세로 R 가로 C # 같은 알파벳 통과 불가 # (0,0) 포함 시작 def dfs(c, x, y): global answer if answer < c: answer = c for k in range(4): nx = x + dx[k] ny = y + dy[k] if 0
[코딩인터뷰] 백준 10026번 BFS from collections import deque # R G B 적록 색약 시 R = G n = int(input()) pic = [] for _ in range(n): pic.append(list(input())) dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] v_a = [[False] * n for _ in range(n)] v_b = [[False] * n for _ in range(n)] c_a = 0 c_b = 0 for i in range(n): for j in range(n): if not v_a[i][j]: rgb_a = pic[i][j] q_a = deque() q_a.append((i, j)) v_a[i][j] = True c_a += 1 if not v..
[코딩인터뷰] 백준 2468번 Python 으로 DFS 전략으로 풀면 'Recursion Error' 나고 '메모리 초과' 나고 난리납니다. 그래서 BFS 로 바꿔서 풀어야 합니다. 전에는 DFS 가능했는데 메모리가 줄었나 봅니다. BFS from collections import deque # 2
[코딩인터뷰] 백준 2638번 from collections import deque # 5
[코딩인터뷰] 백준 2146번 from collections import deque import sys sys.setrecursionlimit(10000) def create_island(id, x, y): global sea, islands, iv, dx, dy sea[x][y] = id islands[id].append((x,y, 0)) iv[x][y] = True for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0
[코딩인터뷰] 백준 16236번 from collections import deque # 크면 못지나감. 같으면 지나감. 작아야 먹음 # 자기 크기만큼 먹어야 성장 n = int(input()) space = [] for _ in range(n): space.append(list(map(int, input().split()))) # 아기상어 처음 위치 shark_loc = (0, 0) for i in range(n): for j in range(n): if space[i][j] == 9: space[i][j] = 0 shark_loc = (i, j) # 아기 상어 처음 크기 shark_level = 2 shark_eat_count = 0 # 시간 time = 0 # 이동 dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1..
[코딩인터뷰] 백준 14502번 백준 14502번 연구소 문제는가능한 경우의 수가 많지 않습니다. 그래서 무식하게 벽을 세울 수 있는 모든 경우의 수를 검토해도 시간 안에 풀 수 있습니다. 만약 이게 문제가 아니었다면 바이러스를 기준으로 탐색해서 벽을 더 효율적인 세울 수 있는 방법을 찾아보고 싶네요. from copy import deepcopy from collections import deque def virus(): global n, m, maps, answer, viruses, dx, dy c_maps = deepcopy(maps) for v in viruses: q = deque() q.append(v) visited = [[False] * m for _ in range(n)] while 0 < len(q): c = q.po..
[코딩인터뷰] 백준 15686번 def set_min(chicken): global n global city global answer total = 0 for i in range(n): for j in range(n): if city[i][j] == 1: dists = [] for c in chicken: dists.append(abs(c[0] - i) + abs(c[1] - j)) total += min(dists) if total < answer: answer = total def dfs(chicken, x, y): global n global m global city if len(chicken) == m: set_min(chicken) return for i in range(x, n): t = 0 if x != i else y f..

티스토리툴바