프로그래머스 LV3

[프로그래머스 LV3] 단어 변환 (BFS, DFS) [C++, JAVA]

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 단어 집합이 주어지고, 시작 단어에서 타깃 단어까지 몇 번만에 바꿀 수 있는지 리턴하는 문제이다. 그 대신, 단어는 한 글자만 바꿀 수 있다. 나는 처음에 DFS+백트래킹으로 단어의 문자 알파벳 하나하나를 바꿔가면서 ex) abc bbc cbc dbc ebc... 만약에 그 단어가 단어 집합에 ..

[프로그래머스 LV3] 가장 먼 노드 (BFS) [C++]

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 1번 노드로부터 최단 거리 중 가장 먼 노드들의 개수를 찾는 것이다. 즉, 1번으로부터 4번 5번 6번 노드의 최단 거리가 3이고 그 거리가 그래프에서 1번과 가장 먼 거리면 정답은 3이다. 따라서 나는 input을 인접 리스트에 저장하고, BFS를 수행해서 최단거리를 찾으면 되겠다고 생각했다. #include #include #include using namespace std; vector v[20001]; int check[20001], re..