Algorithm 검색 결과

해당 글 225건

[BFS] 2206번 벽 부수고 이동하기

2206_벽 부수고 이동하기 2206번 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤..
Algorithm/BOJ 문제풀이 2018. 11. 28. 19:33

[BFS] 6593번 상범 빌딩

6593_상범 빌딩 6593번 상범 빌딩 https://www.acmicpc.net/problem/6593 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다. 당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까? 입력 입력은 여러 개의 테스트 케이스로 이..
Algorithm/BOJ 문제풀이 2018. 11. 27. 19:18

[Dijkstra] 4485번 녹색 옷 입은 애가 젤다지?

4485_녹색 옷 입은 애가 젤다지? 4485번 녹색 옷 입은 애가 젤다지? https://www.acmicpc.net/problem/4485 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 ..
Algorithm/BOJ 문제풀이 2018. 11. 27. 15:50

[Dijkstra] 1261번 알고스팟

1261_알고스팟 1261번 알고스팟 https://www.acmicpc.net/problem/1261 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NM 크기이며, 총 11크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.벽은 평소에는 이동..
Algorithm/BOJ 문제풀이 2018. 11. 25. 21:37

[Algorithm] 탐색 알고리즘

탐색 알고리즘 탐색 알고리즘 미로 탐색 알고리즘 다익스트라 알고리즘 ✅ DFS (Depth First Search) '깊이 우선 탐색' 을 뜻한다 스택 또는 재귀를 사용한다 탐색이 막히면 다시 돌아와 다른 곳을 탐색 할 수 있다 (백트래킹) ✅ BFS (Breadth First Search) '너비 우선 탐색' 을 뜻한다 큐(Queue)를 사용한다 탐색이 끝난 노드는 큐에서 삭제 (pop) 한다 ✅ BFS 최단 경로 위 문제의 포인트는 BFS 탐색으로 (0, 0)을 시작으로 해서 맵의 모든 이동 가능한 경로를 움직일 때 마다 비용을 '1'씩 더해주고 최종 (N,M) 을 만나면 종료하도록 해야함 ✅ 다익스트라 알고리즘 (Dijkstra Algorithm) 주어진 시작 지점에서 모든 지점의..
Algorithm/알고리즘 2018. 11. 25. 21:11

[Dijkstra] 1238번 파티

1238_파티 1238번 파티 https://www.acmicpc.net/problem/1238 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. 입력 첫째 줄에 N(1 ..
Algorithm/BOJ 문제풀이 2018. 11. 24. 14:13

[Dijkstra] 1504번 특정한 최단 경로

1504_특정한 최단 경로 1504번 특정한 최단 경로 https://www.acmicpc.net/problem/1504 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.라 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 ..
Algorithm/BOJ 문제풀이 2018. 11. 24. 14:11

[Dijkstra] 1916번 최소비용 구하기

1916_최소비용 구하기 1916번 최소비용 구하기 https://www.acmicpc.net/problem/1916 문제 N의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 ..
Algorithm/BOJ 문제풀이 2018. 11. 22. 20:13