그래프, BFS/DFS 문제https://www.acmicpc.net/problem/1967 트리의 지름 트리의 지름이란?어떤 두 노드를 선택해서 당겼을 때, 가장 길게 늘어나는 경우의 두 정점 사이의 거리를 말한다.즉, 트리의 지름이란 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다.위의 그래프에서 9 노드와 12 노드의 사이의 거리는 45이며, 이 경로가 트리의 지름이 된다. 트리의 지름을 구하는 순서1. DFS를 통해 임의의 정점(x)로부터 가장 먼 정점(y)를 구한다.2. DFS를 통해 구해진 (y) 정점으로부터 가장 먼 정점(z)를 구한다.3. (y) 정점과 (z) 정점을 잇는 경로가 트리의 지름이 된다.  💡 풀이코드 (성공 - DFS)# DFS# visited 초기화 주의 im..

BFS, DFS 문제https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 접근방식숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수 구하기 -> DFS로 풀어 모든 경우의 수 탐색특정 숫자를 변환하였을 때의 타겟 넘버를 만족하는지를 비교하여 가짓수(경우의 수) 구하는 것이므로 return값 설정 풀이코드  (실패, 오답-cnt를 전역변수로 선언)import syssys.setrecursionlimit(10 ** 9)cnt = 0oper = [1, ..

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr BFS 문제  문제코드from collections import dequedef bfs(queue, words, target): while queue: now, counts = queue.popleft() if target == now: return counts for i in range(len(words))..

Dijkstra 문제https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존www.acmicpc.net 💡 풀이코드 1  (성공)import sysimport heapqimport copynode, edge = map(int, sys.stdin.readline().split())graph = [[] for _ in range(node + 1)]visited = [[False] for _ in range(node + 1)]for i in ..

BFS + 백트래킹 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크www.acmicpc.net 0 - 빈 칸1 - 벽2 - 바이러스 처음에 생각한 방식 이것도 처음에 패턴 찾아서 쌩자 구현하려 했는데, 불가능이다. 그 이유는 바이러스(2)가 벽(1)을 만날때까지 상하좌우로 이동하며 벽(0)을 바이러스(2)로 감염시키기 때문이다. 즉, 패턴을 찾을 수 없다. 접근 방식바이러스들(2)의 위치에서 동시에 퍼져야 하므로 BFS벽을 무조건 3개 세워야 하는데, 바이러스가 최대한 퍼지지 않는..

BFS 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로www.acmicpc.net (1) 처음에 생각한 방식 - V1 (실패)# 벽 부수고 이동하기 (골드 3) / BFSimport sysfrom collections import dequen, m = map(int, sys.stdin.readline().split())graph = [[] for _ in range(n)]visited = [[False] * m for _ in range(n)]..