'BFS' 태그의 글 목록

[프로그래머스] 단어 변환

2024.03.06

✨ BFS/DFS https://school.programmers.co.kr/learn/courses/30/lessons/43163# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📍 고려해야할 점 한 번에 한 개의 알파벳만 변경 가능 begin에서 target으로 변환하는 가장 짧은 변환 과정 찾기 굳이 배열의 순서대로 찾을 필요 없음 🕹️ 풀이과정 👉 이 문제 같은 경우 DFS와 BFS 모두 풀이 가능하다. 하지만 DFS로 구현할 시에는 시간복잡도가 크다. 🔹 DFS words 배열에서 현재 단어와 한 글자만 다른 단어를 탐색한다. 👉 중복 탐색을 방..

알고리즘/BOJ

[BOJ] 18352 특정 거리의 도시 찾기 - Java

2023.12.04

✨ 그래프 탐색 ✨ BFS, 다익스트라 ➔ 최단 경로 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 📍 고려해야할 점 출발 도시에 대한 정보가 존재한다. 최단 거리에 대한 정보가 존재한다. ➔ 해당하는 최단 거리인 도시를 찾으면 된다. 하나의 도시에서 다른 모든 도시까지의 최단거리를 구해야하기 때문에 다익스트라 알고리즘을 사용한다. 도시간의 거리가 모두 1이기 때문..

알고리즘/BOJ

[BOJ] 4179 불! - Java

2023.10.25

✨ BFS ➔ 동시에 이동시키기 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 📍 고려해야할 점 불과 지훈이를 동시에 이동시켜야한다. 동시에 이동시키기 위해서 두 개의 큐를 사용한다. 불은 지훈이의 존재 여부에 대해 영향을 받지 않는다. (지훈이가 있거나 없어도 언제든지 벽만 아니라면 언제든지 전파 가능) 지훈이는 불의 존재 여부에 대해 영향을 받는다. (불이 존재한다면 이동 불가) 지훈이가 가장자리에 도달하면 미로를 통과할 ..

알고리즘/BOJ

[BOJ] 14502 연구소 - Java

2023.09.28

✨ BFS + DFS + 완전탐색 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 📍고려해야할 점 벽을 3개 세운다. ➔ 일일이 3개의 벽을 세워본 후 바이러스를 퍼뜨려 안전영역이 최대인 경우를 구한다. (백트래킹 + 완전탐색) 벽을 3개 세운 후 바이러스가 퍼지는 경우는 다양하므로 복사본을 만들어서 구한다. 🕹️ 풀이과정 1️⃣ 바이러스와 벽이 있는 곳의 정보를 2차원 배열에 저장한다. 2️⃣ 벽을 세운다. ➔ 3개의 벽을 세워야 하므로 조합을 생각하면 ..

알고리즘/BOJ

[BOJ] 1939 중량제한

2023.09.07

✨ Binary Search + BFS/DFS https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 📍 고려해야할 점 두 섬 사이에 여러 개의 다리가 있고 양방향이다. 공장이 있는 두 섬을 연결하는 경로가 반드시 존재한다. (반드시 존재하는 경로의 입력값만 주어짐) 옮길 수 있는 물품의 최대 중량 구하기 🕹️ 풀이과정 1️⃣ 입력값으로 주어진 다리 정보 저장 (a섬과 b섬 사이에 중량제한이 ..

[프로그래머스] 단어 변환

[BOJ] 18352 특정 거리의 도시 찾기 - Java

[BOJ] 4179 불! - Java

[BOJ] 14502 연구소 - Java

[BOJ] 1939 중량제한

티스토리툴바