BFS
-
BOJ) 다리 만들기알고리즘/백준 2021. 2. 14. 23:20
다리 만들기 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 여러 섬으로 이루어진 나라에서 가장 가까운 두 섬을 잇는 최단 거리 비용을 구하는 문제다. 최단 거리라고해서 해당 알고리즘들을 사용할 수 있을까 고민했는데, 떠오르지 않았다. 그래서 평소에 즐겨하던 grouping을 하면서, 모든 섬마다 전체 좌표를 List에 저장했다. 또한, 각 섬마다 위치를 식별할 수 있어야해서 위의 섬의 좌표를 저장하는 List를 List에 저장해주었다. List 으로 섬의 모든 좌표를 저장해주었다. 좌표를 모두 저장한 이후에는 각..
-
BOJ) 치즈알고리즘/백준 2021. 2. 5. 18:24
치즈 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 처음에는, 4면을 검사하면서 공기와 접촉하지 않은 치즈들의 지워지는 시간을 1시간씩 증가 시켰었다. 하지만, 문제의 조건에서 모든 공기가 치즈를 녹이는 것이 아니라, 가장 외부에 있는 공기들만 치즈를 녹인다는 조건이 있었다. 또한, 맵의 테두리는 공기로만 주어진다는 조건이 있어서 BFS를 이용했다. 외부 공기의 위치와 가장 외부에 노출된 치즈의 위치를 저장할 큐 두 개를 선언해주었다. 0,0을 시작으로 외부 공기를 큐에 저장하면서, 가장 외부에 닿은 치즈들의 좌표 또한 다른 ..
-
BOJ) 캐슬 디펜스 (17135 번)알고리즘/백준 2021. 2. 3. 18:03
캐슬 디펜스 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 생각보다 많이 어려웠던 문제였다. 적을 제거하는 규칙을 찾아 글로는 정리가 됐지만, 어떻게 코드로 구현해야할지 감이 오질 않았다. 그래서, 다른 블로그 글을 찾았고, 여기글을 많이 참고했다. 궁수가 적을 죽이는 순서는 삼각형을 그렸을 때, 좌측, 상단, 우측의 꼭지점 순서라고 생각하면 편하다. 공격 범위에 따라 위와 같은 순서로 적을 죽이게 된다. 범위 : 1 => y-1 범위 : 2 => (x-1,y-1) ~> (x, y-2) ~> (x+1, y-1) 이런 식..
-
BOJ) 숫자고르기알고리즘/백준 2020. 8. 28. 16:42
숫자고르기 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절� www.acmicpc.net 풀이 어제 풀었던 사이클 문제와 비슷한 것 같은데, 이 문제는 BFS로 풀었다. (사실 어제 푼 방법이 기억에 남지 않았다.) 1~N번까지 순회하면서 해당 인덱스가 가진 값을 타고 가는 검사를 통해, 시작한 인덱스 i번이 나오면 답에 추가를 해줬다. 위의 값을 가지고 있다면, 1번~ 7번까지 순회를 하면서 답을 찾는 것이다. 1번 index는 3이라는 값을 가지고 있다. 이 3이라는 값을 LinkedList에 넣고, 탐색을 한다. 3번 ..
-
BOJ) 섬의 개수알고리즘/백준 2020. 8. 26. 15:38
섬의 개수 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net 풀이 섬의 개수를 찾는 문제로, 인접한 8구역이 땅이면 이동할 수 있다는 조건을 가지고 있다. 제약 조건이 기존 4곳에서 대각선들만 추가됐을뿐, 일반적인 grouping 문제다. grouping 문제는 이전 문제들에서 많이 다뤘기 때문에 큰 풀이는 남기지 않으려고 한다. 다만, 좌 우의 상/하 대각선을 예외처리 없이 검사하기 위해 map의 크기를 입력받은 n,m값 +2로 설정해줬다는 점이 특이하다 정도는 주의할만 하다. 그리고, 한 메소드 당 하나의 기능만 ..
-
BOJ) 트리의 부모 찾기 (11725, JAVA)알고리즘/백준 2020. 8. 25. 17:58
트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 처음에는 1차원 배열로 문제를 풀려고 하다가, 연결 관계에서 부모 관계를 파악하기 힘들다는 문제를 발견했다. 그래서 BFS로 풀어야겠다는 마음을 먹었다. 우선 map을 저장해줘야 하는데, 배열을 사용할 수 없다. (최악의 경우 100,000 by 100,000가 된다) 그래서, ArrayList 배열에 map의 관계를 저장했다. (레코드 조회만 필요하기 때문에 ArrayList가 더 적절하다고 판단했다.) 맵이 저장된 다음에는 Queue를 통해 부모를 짝지어주었다. root인 1부터 시작하면서 1과 연결..
-
BOJ) 촌수 계산알고리즘/백준 2020. 8. 1. 23:55
촌수 계산 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net 풀이 문제 의미대로 촌수를 계산하는 코드를 짜야한다. 다른 질문게시판을 보면 여러 알고리즘을 언급하고, 2차원 배열을 통해 푸는 것 같았다. 2차원 배열까지 갈 필요가 없다고 느껴서 1차원 배열로 풀었다. 우선 주어지는 값을, 1차원 배열에 저장했다. 저장하는 배열의 index는 자식 노드의 번호가 되고, value는 부모 노드를 입력해줬다. 부모 노드의 경우 자식 노드가 1개 이상 존재할 수 있기 때문이다. 그리고, 해당 노드들이 p..
-
BOJ) 로봇 청소기알고리즘/백준 2020. 7. 24. 22:47
로봇 청소기 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 푸는데 많은 시간을 소요했다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 네 방..