본문 바로가기
728x90
반응형

코딩테스트/백준104

[백준/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.
[백준/java] 7576번 : 토마토 - BFS https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ※ 문제 풀이방식 BFS가 응용된 부분 위주로 설명 드리겠습니다 (1) 우선 dy, dx 배열의 값은 두개의 값들을 함께보면 (1, 0), (0, 1), (-1, 0), (0, -1) 이 순으로 되어있습니다. --> 이것이 의미하는 것은 북 동 남 서 방향으로 방향을 설정하는 것입니다. (2) Node 클래스에 기존에 풀이했던 그림, 섬의 개수, 안전 영역같은 문제들과는 달리 x,.. 2021. 8. 14.
728x90
반응형

티스토리툴바