본문 바로가기

Algorithm/Graph Search Algorithm30

BOJ G3 16954 움직이는 미로 탈출 JAVA 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 문제 읽기 처음에 딱 읽었을 때는 DFS가 생각났다. 그래서 dfs로 짜다가.. 생각해보니 벽을 피해서 움직여야 하고, 8방으로 움직여야 한다. 맵의 크기가 매우 작긴 하지만, 벽을 피해서 이동하는게 최우선이기 때문에 중복 방문도 가능하다 생각했고, 경우의 수가 너무 많이 나올 것 같았다. 맵의 벽도 계속 이동 시켜서 넘겨줘야 하는데 너무 비효율적이라는 생각이 들었다. 게다가 DFS의 재귀 + 중복 방문 허용이 합쳐지면 처리를 해주지 않는 이상 무한 루.. 2024. 2. 20.
BOJ G3 2151 거울 설치 JAVA 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 문제 읽기 처음에 문제를 읽었을 때에는 dfs를 써야겠다고 생각했다. 그렇게 풀었는데 백트래킹을 제대로 하지 않아서 인지.. 3%에서 계속 시간 초과가 났다 !! 너무 답답해서 그냥 풀이 방식을 바꿔보기로 했다. 글 읽기 - 어디가 틀렸을까요 ㅠ 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 위 글을 통해 힌트를 얻었다. 0-1 BFS를 이용하면 될 것 같았다. 잊고 있었던 알고리즘이다. 문제 풀기 0-1 BFS는 BFS처럼 방문.. 2024. 2. 19.
BOJ G4 11404 플로이드 JAVA 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 읽기 문제는 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제이다. 근데 알고리즘을 어떤 걸 써야 하는지는 문제 이름에서 스포를 당하긴 했지만.. 플로이드 워샬 알고리즘이 잘 기억이 나지 않아서 처음엔 그냥 다익스트라를 N번 돌렸다. 그래도 플로이드 워샬 알고리즘도 정리할 겸 공부해서 다시 풀어보았다. 문제 풀기 다음과 같이 다익스트라와 플로이드 워샬로 풀었다. 다익스트라 모든 정점에서 다른 모든 정점까지의 최단 거리니까 다음 코드와 같이 모든 노.. 2024. 2. 17.
Floyd-Warshall, 플로이드 워샬 알고리즘 그래프 문제에서 최단 경로를 구하는 알고리즘은 다음과 같다. Dijkstra 다익스트라 한 지점에서 다른 모든 지점까지 최단 거리 양의 가중치만 O(ElogV) Bellman-ford 밸만-포드 한 지점에서 다른 모든 지점까지 최단 거리 음의 가중치 허용 O(VE) Floyd-Warshall 플로이드 워샬 모든 지점에서 다른 모든 지점까지 최단 거리 음의 가중치 허용 O(V^3) 다익스트라와 밸만 포드에 대해서는 다음 포스팅에서 알아볼 수 있다. 다익스트라, Dijkstra Algorithm 코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. 다익 rue-mi.tistory.. 2024. 2. 17.

티스토리툴바