Notice
Recent Posts
Recent Comments
Link
HwangHub
[BFS/자바] 코드트리 IL. K번 최댓값으로 이동하기 본문
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
문제 해석
위 문제는 2차원 배열 위에서 상하좌우로 움직이며 최댓값을 찾는 것을 반복하되, 움직이는 과정에서 무한으로 돌지 않도록 방문한 곳은 두번 방문하지 않아야 하며, 처음 시작한 곳의 숫자보다 작은 곳만 탐색할 수 있다.
이러한 방식은 그래프 알고리즘으로 구현이 가능하다. 일단은 코드트리에서 의도한 방향이 BFS이므로 BFS로 구현해보고, 나중에 다시 풀때 DFS로 가능한지 한번 살펴볼 예정이다.
문제 풀이
package 코드트리.그래프.BFS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class K번_최댓값으로_이동하기 {
private static int n, k;
private static int[][] arr;
private static int[][] visited;
private static int startNum;
private static int ansX, ansY, ansNum;
private static int startX, startY;
private static Queue<Pair> q = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
arr = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
startY = Integer.parseInt(st.nextToken())-1;
startX = Integer.parseInt(st.nextToken())-1;
for (int i = 0; i < k; i++) {
visited = new int[n][n];
startNum = arr[startY][startX];
Pair startPoint = new Pair(startY, startX);
q.add(startPoint);
ansY = n;
ansX = n;
ansNum = 0;
bfs();
if (ansY < n && ansX < n) {
startY = ansY;
startX = ansX;
}
}
System.out.println((startY+1) + " " + (startX+1));
}
private static void bfs() {
int[] dy = new int[]{0, 1, 0, -1};
int[] dx = new int[]{1, 0, -1, 0};
while (!q.isEmpty()) {
Pair crt = q.poll();
int crtX = crt.x;
int crtY = crt.y;
for (int i = 0; i < 4; i++) {
int newX = crtX + dx[i];
int newY = crtY + dy[i];
if (canGo(newY, newX)) {
push(newY, newX);
}
}
}
}
private static void push(int y, int x) {
visited[y][x] = 1;
if (arr[y][x] <= startNum && x != startX || y != startY) {
if (ansNum < arr[y][x]) {
ansY = y;
ansX = x;
ansNum = arr[y][x];
} else if (ansNum == arr[y][x]) {
if (y < ansY) {
ansY = y;
ansX = x;
ansNum = arr[y][x];
} else if (y <= ansY && x < ansX) {
ansX = x;
ansNum = arr[y][x];
}
}
}
q.add(new Pair(y, x));
}
private static boolean canGo(int y, int x) {
if (!inRange(y, x) || visited[y][x] == 1 || arr[y][x] >= startNum) {
return false;
}
return true;
}
private static boolean inRange(int y, int x) {
return y >= 0 && y < n && x >= 0 && x < n;
}
private static class Pair {
private int x;
private int y;
private Pair(int y, int x) {
this.x = x;
this.y = y;
}
}
}완전 초창기 로직에서는 처음 시작 위치의 수보다 큰 수만 제외하는 것이라 생각해서 push 로직을 구성할 때, 시작점이 ansX, ansY에 반영되는 것을 막아야 한다 판단했고, 이를 위해 startX, startY라는 변수를 추가해서 이를 구분해 줘야겠다고 생각했었다.
하지만 문제를 자세히 읽어보니 시작점보다 더 작은 수로만 이동할 수 있으므로, 시작점이 ans 후보에 올라가는 경우는 이미 canGo에서 필터링할 수 있으므로 크게 고려하지 않아도 되는 케이스였다.
위 로직으로 통과는 하였지만, 필요 없는 로직이 많이 들어가 있는 것이다. 따라서 필요 없는 로직을 덜어내어 최적화한 로직은 아래와 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int n, k;
private static int[][] arr;
private static int[][] visited;
private static int startNum;
private static int ansX, ansY, ansNum;
private static Queue<Pair> q = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
arr = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
int startY = Integer.parseInt(st.nextToken())-1;
int startX = Integer.parseInt(st.nextToken())-1;
for (int i = 0; i < k; i++) {
visited = new int[n][n];
startNum = arr[startY][startX];
Pair startPoint = new Pair(startY, startX);
q.add(startPoint);
ansY = n;
ansX = n;
ansNum = 0;
bfs();
if (ansY < n && ansX < n) {
startY = ansY;
startX = ansX;
}
}
System.out.println((startY+1) + " " + (startX+1));
}
private static void bfs() {
int[] dy = new int[]{0, 1, 0, -1};
int[] dx = new int[]{1, 0, -1, 0};
while (!q.isEmpty()) {
Pair crt = q.poll();
int crtX = crt.x;
int crtY = crt.y;
for (int i = 0; i < 4; i++) {
int newX = crtX + dx[i];
int newY = crtY + dy[i];
if (canGo(newY, newX)) {
push(newY, newX);
}
}
}
}
private static void push(int y, int x) {
visited[y][x] = 1;
if (ansNum < arr[y][x]) {
ansY = y;
ansX = x;
ansNum = arr[y][x];
} else if (ansNum == arr[y][x]) {
if (y < ansY) {
ansY = y;
ansX = x;
ansNum = arr[y][x];
} else if (y <= ansY && x < ansX) {
ansX = x;
ansNum = arr[y][x];
}
}
q.add(new Pair(y, x));
}
private static boolean canGo(int y, int x) {
if (!inRange(y, x) || visited[y][x] == 1 || arr[y][x] >= startNum) {
return false;
}
return true;
}
private static boolean inRange(int y, int x) {
return y >= 0 && y < n && x >= 0 && x < n;
}
private static class Pair {
private int x;
private int y;
private Pair(int y, int x) {
this.x = x;
this.y = y;
}
}
}사실 깔끔하진 않은 것 같고, 더 최척화할 요소가 분명 있을 것이라 생각한다. 아직 알고리즘 구성 역량이 부족해서 바로바로 머리에 그려지지 않다보니 이것저것 틀어막으려고 변수를 추가하게 되는 것 같다. 더 많이 풀어보면서 로직 구성 역량을 더 키워야함을 느낀다...
그래도 어제부터 푼건데... 포기않고 풀어내서 나름으로썬 뿌듯하다.
누군가에게 1rm이 누군가에겐 몸풀기 무게임을 인정하고, 그저 정진할 뿐...
'workspace > 알고리즘' 카테고리의 다른 글
| [BFS/자바] 코드트리 IL. 우리는 하나 (1) | 2023.10.10 |
|---|---|
| ★[BFS/자바] 코드트리 IL. 돌 잘 치우기 (틀림, 나중에 다시 풀어보자) (0) | 2023.10.07 |
| [완전탐색/자바] 코드트리 IL. 컨베이어 벨트 (0) | 2023.10.01 |
| [완전탐색/자바] 코드트리 IL.양수 직사각형의 최대 크기 (0) | 2023.09.29 |
| [완전탐색/자바] 코드트리 IL. 행복한 수열의 개수 (0) | 2023.09.28 |
'workspace/알고리즘' Related Articles
more
Comments