Devlog

https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr from collections import deque def bfs(start, end, maps): answer = 0 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] row, col = len(maps), len(maps[0]) check = [[0] * col for _ in range(..

BFS (Breadth First Search, 너비 우선 탐색) 시작 정점으로부터 거리가 가까운 정점 순(너비 우선)으로 인접한 노드를 탐색하는 알고리즘 특징 - 최단 경로를 찾을 때 사용 - 일반적으로 큐(Queue) 사용 (선입선출 방식을 사용해야 함) - 재귀적 x - 시간복잡도 : 인접 리스트로 구현된 경우 O(|V|+|E|), 인접 행렬로 구현했을 경우 O(|V|^2) - 입력 : 노드의 갯수 n, 그래프 graph, 시작 노드 v 장점 - 최단 경로를 보장 - 단순 검색 속도가 DFS보다 빠르다. 단점 - 경로가 긴 경우 많은 메모리를 필요로 한다. Python 구현 코드 n = 6 graph = {1: [3, 2], 2: [3, 1, 4, 5], 3: [6, 4, 2, 1], 4: [3, ..

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr from collections import deque def solution(n, edge): answer = 0 graph = {i:[] for i in range(1, n+1)} for i, j in edge: graph[i].append(j) graph[j].append(i) visited = [0] * (n+1) visited[1] = 1 queue = deque([[1, 0]]) while(queue): node, dept..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr def solution(begin, target, words): if target not in words: return 0 answer = 0 start = [begin] while(len(words) != 0): for s in start: tmp = [] for word in words: cnt = 0 for i i..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net from collections import deque # 상, 하, 좌, 우 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] def bfs(x, y): q.append([x, y]) check[x][y] = 1 while(q): x, y = q.popleft() for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net N, M, V = map(int, input().split()) s = [[0] * N for i in range(N)] check = [0 for i in range(N)] def dfs(v): check[v-1] = 1 print(v, end = ' ') for i in range(..