728x90 반응형 코딩테스트190 [백준/java] 1987번 : 알파벳 - DFS https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제풀이 처음으로 DFS를 사용해서 풀어봤다. 골드 4 난이도 치고는 문제 자체는 어렵지 않다 나왔던 알파벳이 또 나오면 더 이상 진행하지만 않으면 되는데, 나는 HashSet을 이용하여 중복으로 나온건지 체크하였다. package dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStrea.. 2021. 8. 19. [백준/java] 2589번: 보물섬 - BFS, 브루트포스 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 브루트 포스와 BFS 탐색이 결합된 문제이다. 처음에 어떻게 보물의 위치를 구해야하나 싶었지만 같이 풀은 친구의 힌트로 두 점의 위치를 구할 필요가 없다.(브루트 포스라서!) 이중 for문으로 무차별 대입을 해줘서 step이 가장 큰, 즉 두 점 사이의 거리가 가장 큰 값을 반환하면 된다. 두 점 사이의 거리가 가장 먼 곳이 보물의 위치이기 때문에, 그냥 거리값만 반환하면 된다. package bfs.. 2021. 8. 18. [백준/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. 이전 1 ··· 5 6 7 8 9 10 11 ··· 32 다음 728x90 반응형
