탐색 (13) 썸네일형 리스트형 [Baekjoon]17070.파이프 옮기기1 17070.파이프 옮기기1 http://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 문제를 읽어보니 바로 전에 풀었던 SWEA의 탈주범검거 문제와 비슷하다는 느낌을 받았다. 일단 현재.. [SWEA]1953.탈주범 검거 bfs로 푸는 문제였다. 그런데 파이프가 연결되어 있는 지점으로만 이동이 가능하기 때문에 현재지점에서 상하좌우를 확인하여 연결이 된 지점으로만 탐색을 수행해야한다. 현재 지점의 파이프 번호에 따라서 탐색할 수 있는 방향이 정해져 있다. 예를 들면 현재 지점의 파이프번호가 2번이면 어차피 좌우로는 이동할 수 없기 때문에 상하 방향만 탐색하도록 한다. 이처럼 파이프 번호에 따라 탐색할 방향을 for문 안에서 미리 걸러주었다. 문제를 풀 때 한가지 착각을 했다. y좌표가 + 되는 것이 아래로 이동하는 방향이고 - 되는 것이 위로 이동하는 방향인데 이것을 반대로 생각해서 계속 틀렸다. 방향에 주의하자. private static void bfs() { visited[R][C] = true; q.add(new P.. [Baekjoon]1987.알파벳 1987.알파벳 http://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net dfs + 백트래킹으로 풀었다. 말이 움직일 수 있는 최대 칸 수를 구하는 것이므로 dfs로 최댓값을 갱신하면서 풀었다. SW.. [SWEA]1949.등산로 조성 dfs + 완전탐색으로 풀었다. 처음엔 백준의 벽 부수고 이동하기와 비슷하다고 생각해서 bfs로 접근했지만 가능한 길게 등산로를 만들어야 하기 때문에 dfs로 푸는게 일반적인 풀이라는 것을 알았다. 봉우리들을 찾는다. 봉우리마다 등산로 조성을 해본다. 인접한 곳이 내리막길이 아니면 1씩 깎아보면서(K까지만) 내리막이 되면 탐색을 계속한다. 먼저 맵에서 가장 높은 곳의 높이를 highest에 저장하고 그 지점들을 peak배열에 삽입한다. peak배열에서 봉우리를 하나씩 꺼내서 탐색을 한다. 탐색을 할 때 이전에 지형을 깎는 공사를 했는지 안했는지 여부를 체크하기 위해 flag 변수를 사용한다. 지형을 깎는 공사를 이미 했다면 더 이상 깎는 공사를 할 수 없으므로 현재 지점보다 낮은 지점으로만 탐색을 계속해.. [Baekjoon]14442.벽 부수고 이동하기2 14442. 벽 부수고 이동하기2 http://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 벽 부수고 이동하기 문제에서 벽을 부술 수 있는 개수가 K개로 주어지는 문제이다. 벽을 부술 수 있는 개수가 최대 1개에서 최대 K개로 바뀐 것이다. 부술 수 있는 벽의 개수가 K개로 늘어났으므로 visited배열의 크기도 늘려줘야 한다. visited[y][x][벽을 부순 개수 : 0 ~ K] nextC = curC + 1 로 .. [Baekjoon]2206.벽 부수고 이동하기 2206.벽 부수고 이동하기 http://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 미로 탐색과 비슷한 문제지만 벽을 최대 1개까지 부술 수 있다는 점이 다르다. 조건에 따라 bfs를.. [Baekjoon]5427.불 5427.불 http://www.acmicpc.net/problem/5427 5427번: 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩 www.acmicpc.net 3055.탈출과 거의 같은 문제였다. 다른 점은 이 문제에서는 도착지점이 맵에 주어져있지 않고 맵 밖으로 빠져나가야 탐색이 끝난다는.. [Baekjoon]2146.다리만들기 2146.다리만들기 http://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은, 섬들을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서 www.acmicpc.net dfs와 bfs를 모두 사용하여 풀 수 있는 문제였다. 크게 두 부분으로 나누어서 풀었다. 섬을 구분짓는다.(dfs.. 이전 1 2 다음
