백준 문제풀이(JAVA)/그래프 탐색 (7) 썸네일형 리스트형 백준 1194번 달이 차오른다, 가자(JAVA) 비트연산, 비트마스킹과 문자만 좀 다룰 줄 알면 쉽게 풀 수 있는 BFS문제 출처 : https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net import java.util.*; import java.io.*; class Node { int y;//y좌표 int x;//x좌표 int count;//여태까지 움직인 횟수 int bit;//가지고 있는 열쇠 Node(int y,int x,int count,int bit) { t.. 백준 11559번-Puyo Puyo(JAVA) https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 개인적으론 골4보단 높아야된다고 생각한다. 골 2~3정도?? 중력으로 뿌요뿌요들이 떨어지는 부분은 스택으로 구현하였다. 한 열 을 기준으로 맨 위 행부터 탐색해서 만약 "." 이 아니라면 스택에 넣어준다. 그리고 그 부분은 "."으로 만들어준다. 그렇게 모든 행을 탐색하고 나서 맨 아래행부터 스택에서 pop을 시켜준다. import java.util.*; import ja.. 백준 16236번 -아기상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS이지만 신경써줘야 할게 많아서 까다로운 문제이다. 필자도 몇번의 시도끝에 풀었다. 많은 풀이들이 있지만 나는 나만의 방식으로 풀었다. 먹이의 최단거리는 어떻게 구했는가?? 우선순위 큐를 사용해서 count, y좌표 ,x 좌표 순서로 오름차순으로 정렬했다. 이렇게 되면 같은 거리일때 더 위쪽에 있고, 만약 같은 y좌표라면 더 왼쪽에 있는 좌표를 선택하게 될것이다. 처음 Node를 만들 .. 백준 17472번(JAVA) 이번에 푼 문제는 크게 3가지 단계를 걸치면 된다. 1.섬별로 번호 붙이기 2.섬간의 다리(간선)정보 넣기 3. 2번을 통해 나온 섬간의 간선정보를 바탕으로 프림알고리즘을 수행하여 최소스패닝트리, 즉 각 섬을 모두 연결하는데 필요한 최소한의 비용을 구한다. 섬별로 번호를 붙이는건 어렵지 않다. 0이아닌 땅을 밟으면 BFS를 실행해주어 연결된 모든 1을 한 섬으로 지정한다 이 때 변수 islans_cnt변수가 BFS를 실행할때마다 +되어서 번호를 붙여준다. 그 후 섬간의 다리 정보를 입력받는데 꽤나 까다로운 조건이 붙어있다. 그렇기에 그점에 잘 유의해서 if문을 작성해준다 필자는 오른쪽,왼쪽,아래쪽,위쪽 4개의 for문을 사용했는데 이걸 한 개의 for문으로 줄일 수 있으면 좋겠다. 마지막으로 프림알고리즘.. 백준 10159번(JAVA) 플로이드-와샬 알고리즘을 이용하는 문제이다. 플로이드-와샬 알고리즘은 최단거리를 찾는 문제에서 가장 간단하다. 3중for문, 이것만 기억하면 된다. 3중for문이니까 당연히 시간복잡도는 O(v^3)이다. 그래서 보통 플로이드-와샬 알고리즘을 사용하는 문제들은 정점의 수가 1000을 넘지 않는 것 같다. 플로이드-와샬 알고리즘에 대한 기본적인 설명은 따로 하지 않겠다. 이 문제에서는 일단 입력을 받을때 1 2 이렇게 받으면 map[1][2]=1, map[2][1]=2 이렇게 했다. 1의 값은 앞에인덱스가 뒤에 인덱스보다 무겁다는 뜻, 2의 값은 앞에 인덱스가 뒤의 인덱스보다 보다 가볍다는뜻이다. 플로이드-와샬 알고리즘을 사용할때 기준점이 되는 k인덱스를 기준으로 map[i][k]==1&&map[k][j]=.. 백준 14442번(JAVA) 벽 부수고 이동하기2 문제이다. 벽 부수고 이동하기1문제랑 매우 유사하기 때문에 같이보면 좋을듯 하다. www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제풀이는 간단하다. 객체를 생성할줄만 알면 문제는 매우 쉬워진다. 객체에는 좌표를 나타내는 x,y 그리고 몇칸째이동중인지를 나타내는 count 마지막으로 벽을 몇개를 부쉈는지를 나타내는 crash변수를 만들어낸다. 또한 BFS에서 필수인 방문체크 배열은 visited[i][j][k].. 백준 1103번(JAVA) 이 문제는 DFS와 다이나믹프로그래밍을 모두 적용시켜야 하는 문제이다. DFS를 진행하는도중 만약 방문된곳을 한번 더 방문했다면 바로 -1을 출력하고 프로그램을 종료시켰다 왜?? 경로에 사이클이 생성되었다는 뜻이기 때문이다. DP배열은 단순히 해당 지점까지의 게임횟수를 의미한다. 그런데 만약 다음지점에서의 dp값이 10이다. 근데 현재 지점에서까지의 게임횟수는 5이면 다음지점으로 넘어갈 필요가 있는가? 답은 X다. 왜냐하면 우리는 최대게임횟수를 찾는것이기 때문이다. 위의 내용을 머리에 넣고 아래 소스코드를 보면 이해가 갈것이다. 소스코드 import java.io.*; import java.util.*; public class Main { public static int N; public static i.. 이전 1 다음