Algorithm/Graph Traversal6 [프로그래머스]단어 변환 / 자바 (BFS/DFS 맛꿀마 문제) https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 DFS와 BFS 모두 풀이가 가능한 문제입니다. 먼저 문제의 요구사항을 살펴보면, 문자열 begin으로부터 문자열 target까지의 변환에 필요한 최소 변환 횟수를 구하는 것이 목표입니다. 단, 변환 조건은 한 번에 한 개의 알파벳만 변환이 가능하다는 겁니다. 즉, A에서 B로의 변환이 가능한 경우는 A와 B를 비교했을 때 한 글자를 제외하고 나머지 글자가 모두 같은 경우라고 생각할 수.. 2024. 3. 23. [백준] 1238. 파티 / Java https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ✔ 문제 풀이 조건 분석 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 각각의 학생들은 파티 장소 X에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 학생들은 최단 시간에 오고 가기를 원한다. 왕복시간이 가장 긴 학생의 소요시간을 구하라. 풀이 학생들은 최단시간에 이동을 원하므로 최단 거리 알고리즘 다익스트라를 생각하였다. 이때, 이동방.. 2023. 8. 17. [백준] 14503. 로봇 청소기 / Java https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 풀이 구현 카테고리에 있던 문제라 그저 구현으로 풀수도 있었지만 DFS를 활용해서도 풀 수 있었다. 문제에 주어진 조건을 찬찬히 읽고 이해하는 것이 중요했다. 풀이 흐름에 대한 상세 설명은 소스 코드에 주석으로 대체한다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; imp.. 2023. 6. 8. [백준] 11725. 트리의 부모 찾기 / Java https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 루트 노드인 1부터 DFS 탐색을 하기 때문에 DFS가 시작되는 노드가 부모가 되고, 이 노드에 연결되어 있으면서 아직 탐색되지 않은 노드를 찾는다면 그 노드가 자식 노드가 되게 된다. 다시 말해, 루트 노드로부터 아직 탐색되지 않은 노드를 탐색하며 해당 노드가 어느 노드로부터 왔는지를 찾아 parent[]에 저장한다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import j.. 2023. 5. 30. 이전 1 2 다음
