알고리즘 풀이/백준43 [BOJ] 16946. 벽 부수고 이동하기 4 - JAVA 🔗 문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS), 깊이우선탐색(DFS) , 분리 집합 풀이 문제는 1의 위치를 0으로 변환하고 인접한 그룹의 0의 갯수의 합을 구하는 문제다. 일일이 1일 때 인접한 0의 갯수를 BFS를 이용해 구하면 시간초과가 발생한다. 분리집합을 통해 해결할 수 있다. 우선, 분리 집합 개념을 이용해 0으로 이루어.. 2023. 2. 10. [BOJ] 16933. 벽 부수고 이동하기3 - JAVA 🔗 문제 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS) 풀이 참고 - https://wngml56.tistory.com/80 [BOJ] 14442. 벽 부수고 이동하기2 - JAVA 🔗 문제 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1.. 2023. 2. 9. [BOJ] 14442. 벽 부수고 이동하기2 - JAVA 🔗 문제 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS) 풀이 참고 - https://wngml56.tistory.com/79 [BOJ] 2206. 벽 부수고 이동하기 - JAVA 🔗 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에.. 2023. 2. 9. [BOJ] 2206. 벽 부수고 이동하기 - JAVA 🔗 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색 풀이 보통 BFS 문제와 다른 점과 핵심은 x 지점에서 벽을 만났을 때, 벽을 부술지 안부술지 2가지 경우가 있다는 것이다. 이해해야 할 것 : 특정 지점에 벽을 부숴서 도착하는 경우가 더 빠를지라도, 벽을 안부수고 이동한 경우가 정답일 수 있다. 좀 더 쉽게 이해하기 위해 예시를 들어보자 .. 2023. 2. 8. [BOJ] 1707. 이분 그래프 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS), 깊이우선탐색(DFS), 이분그래프 풀이 이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠해 모든 정점을 두 가지 색으로 칠할 수 있는 그래프이다. 즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점의 서로 간선으로 연결되어 있지 않은 그래프를 이분 그래프라고 한다. 이분그래프 판단은 .. 2023. 2. 8. [BOJ] 11657. 타임머신 - JAVA (벨만포드) 🔗 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 그래프 이론, 벨만-포드 풀이 벨만 포드 (BellmanFord) 알고리즘 개념 가중 유향 그래프에서 최단 경로를 구하는 알고리즘이다. 벨만 포드 알고리즘 동작 원리는 다익스트라(Dijkstra) 와 유사하다. 차이점은 벨만 포드는 음수 가중치가 존재하는 경우에도 적용할 수 있으며 시간 복잡도가 .. 2023. 2. 7. 이전 1 2 3 4 5 6 7 8 다음
