dfs4 [프로그래머스]단어 변환 / 자바 (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. [백준] 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. [백준] 14502 연구소 / java https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 이 문제는 BFS 카테고리의 문제 목록에서 발견했지만 실상은 BFS와 DFS를 복합적으로 사용해야 하는 문제였다. 각각이 사용되는 부분은 아래와 같다. DFS: 벽을 3개 세우는 경우의 수 탐색 BFS: 위 DFS에서 찾은 각 경우에 대해 바이러스를 퍼뜨리는 과정 탐색 다시 말해, DFS로 BFS를 할 케이스를 골라내는 것이다. 더불어 유의할 점으로 Deep Copy와 Swallow Copy의 차이.. 2023. 5. 29. 이전 1 다음
