728x90 반응형 java226 [백준/java] 2206번: 벽 부수고 이동하기 - BFS https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 지금까지 내가 풀어본 BFS 문제 중에 가장 어려웠던 문제였다. 그냥 기존에 풀던 방법대로 풀다가는 풀리지 않는다. 특히나, 기존에 입력한 int형 2차원 배열 값을 변경해서는 결코 안된다. 지문을 읽다보면 벽이 있을 때, 벽을 한번은 부술 수 있는 기회가 주어진다. 그렇다고 해서 map[ny][nx] = 0; 으로 값을 바꿔버리면 제출했을 때 오답이 된다. 정답을 찾기위.. 2021. 8. 17. [백준/java] 1010번: 다리 놓기 - 조합(Combination), 파스칼의 삼각형 이번 문제는 동적계획법 문제이다. 그냥 정확히 말하면 조합 문제이다. 강 동쪽에서 M개 중에 N개를 골라 다리를 연결하는 것이니 조합 문제인 것이 당연할 것이다. Top Down, Bottom Up 둘 중 하나의 방식으로 풀면 된다. 하지만, Top Down처럼 재귀로 호출하는 방식은 스택오버플로우를 불러 일으키기 쉬운 문제이다. 그래서 Bottom Up 방식으로 문제를 풀면 되는데, 이 문제를 푸는 방법중에서는 파스칼의 삼각형을 보면 좋다. 이와 같은 삼각형 모습을 이루는 구조가 파스칼의 삼각형인데, 이것은 (x - 1)^2 나 (x-1)^3 을 펼쳐 계산하면 위와 같은 계수로 나오는 것을 알수 있다. 파스칼의 삼각형을 적용하여 코드를 구현하면 아래와 같다. package dp; import java... 2021. 8. 16. [백준/java] 2178번: 미로 탐색 - BFS https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제에서는 고려해야할 것이 현재 노드가 방문한 노드인지 확인하는 로직이 필요하고, 또 현재 노드의 좌표가 도착점 좌표와 같을 때 BFS 탐색을 종료하고 찾은 개수를 출력하면 된다. if(visit[cur.y][cur.x]) continue; visit[cur.y][cur.x] = true; if(cur.y == N -1 && cur.x == M - 1) { cnt = cur.step; return; } 아래는 완성된 소스코드.. 2021. 8. 16. [백준/java] 2667번 :단지번호붙이기 - BFS https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ※ 문제풀이 이번 문제는 그림(1926)문제와 방법은 똑같고 다만 BFS 탐색할 때 해당 위치가 중복되는지 한번 더 확인해주면 된다. 탐색하는 위치의 방문 여부를 한번 더 해주지 않으면 단지의 개수가 불필요하게 더 늘어나게 된다. 문제가 됐던 부분은 아래와 같다. List complex = new ArrayList(); for (int i = 0; i < N; i++) { for (int j = 0.. 2021. 8. 16. [백준/java] 7569번 : 토마토(3차원배열) BFS 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net ※ 문제풀이 이번 문제는 2차원 배열로 푸는 토마토 문제(7576)와 방법은 똑같고 다만 3차원배열이어서 동서남북 + 위 아래까지 조회를 해주면 된다. 그러면 7576번 토마토와 비교해서 어떤 것이 추가되었는지 확인해보자. 먼저 변수 선언부 static int[][][] map; static boolean[][][] visit; static int M, N, H; static int[][] dx, dy, dh; static class No.. 2021. 8. 15. [백준/java] 7562번 : 나이트의 이동(체스 나이트의 이동) - BFS https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 토마토 문제처럼 이번 문제도 Queue에 넣는 클래스가 y, x값 말고도 cnt가 하나 더 들어갔다. 이것의 용도는 최단거리를 측정할 때 사용하는 것! 이제 점점 BFS로 순회할 때 최단거리를 계산하는 방법이 조금씩 감이 오는 것 같다. 이 문제에서 int형 이차원 배열이 따로 사용되지는 않았다. 방문하는 곳마다 값을 확인할 필요가 없었기 때문이다. 이 문제를 풀때 오래걸리고 오해했던 것은 도착지로.. 2021. 8. 15. 이전 1 ··· 13 14 15 16 17 18 19 ··· 38 다음 728x90 반응형
