제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.
포인트
해당 문제는 검은색 선을 따라서만 이동할 수 있다는 것이 포인트였습니다.
예를 들어, 도형의 변이 다음과 같을 때 BFS/DFS를 할 때에 문제가 발생할 수 있습니다.
(4,3) -> (4,4) -> (5,3) -> ...
왜냐하면 저희가 현재까지 사용했던 dx/dy 테크닉을 사용하게 되면 (4,3)에서 (5,3)으로 바로 이동할 수 있기 때문입니다.
따라서 저는 Scale(2)을 두어 더 정교하게 이동할 수 있도록 하였습니다.
나중에 답을 구할 때에도 Scale의 값만큼 나누어줘야하는 주의사항이 있습니다.
소스코드
import java.util.*;
class Solution {
int answer = 0;
final int SIZE = 101;
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
int[][] map = new int[SIZE][SIZE];
boolean[][] visited = new boolean[SIZE][SIZE];
Queue<Pair> q = new LinkedList<>();
class Pair {
int x, y, cnt;
public Pair(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
public boolean inRange(int x, int y) {
return 0 <= x && x < SIZE && 0 <= y && y < SIZE;
}
public boolean canGo(int x, int y) {
if(!inRange(x, y)) return false;
if(map[x][y] != 1 || visited[x][y]) return false;
return true;
}
public void bfs(int startX, int startY, int itemX, int itemY) {
visited[startX][startY] = true;
q.add(new Pair(startX, startY, 0));
while(!q.isEmpty()) {
Pair cur = q.poll();
if(cur.x == itemX && cur.y == itemY) {
answer = cur.cnt/2;
return;
}
for(int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if(canGo(nx, ny)) {
q.add(new Pair(nx, ny, cur.cnt + 1));
visited[nx][ny] = true;
}
}
}
}
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
int n = rectangle.length;
for(int i = 0; i < n; i++) {
int x1 = rectangle[i][0] * 2;
int y1 = rectangle[i][1] * 2;
int x2 = rectangle[i][2] * 2;
int y2 = rectangle[i][3] * 2;
for(int p = x1; p <= x2; p++) {
for(int q = y1; q <= y2; q++) {
if(p == x1 || p == x2 || q == y1 || q == y2) {
if(map[p][q] == 0) {
map[p][q] = 1;
}
} else {
map[p][q] = 2;
}
}
}
}
bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
return answer;
}
}
코드 설명
- Pair 클래스
- 좌표를 나타내는 x와 y를 저장하는 좌표와 현재 step의 값을 저장하는 클래스입니다.
- BFS 탐색 시 현재 위치를 나타내기 위해 사용됩니다.
public boolean inRange(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
public boolean canGo(int x, int y) {
if(!inRange(x, y)) return false;
if(visited[x][y] || globalMaps[x][y] == 0) return false;
return true;
}
- inRange 메소드
다음 탐색해야하는 좌표가 배열 내부인지 확인하기 위한 메소드
- canGo 메소드
다음 탐색해야하는 좌표로 이동이 가능한지 확인하기 위한 메소드(배열 내인지, 방문한 좌표인지, 다음 좌표가 벽인지)
public void bfs(int startX, int startY, int itemX, int itemY) {
visited[startX][startY] = true;
q.add(new Pair(startX, startY, 0));
while(!q.isEmpty()) {
Pair cur = q.poll();
if(cur.x == itemX && cur.y == itemY) {
answer = cur.cnt/2;
return;
}
for(int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if(canGo(nx, ny)) {
q.add(new Pair(nx, ny, cur.cnt + 1));
visited[nx][ny] = true;
}
}
}
}
- bfs 메소드
- 큐에 현재 위치와 이동 횟수를 저장합니다.
- 상하좌우 네 방향을 탐색하며 이동 가능(canGo)한 경우 큐에 추가합니다.
- 목표 위치(itemX, itemY)에 도달하면 이동 횟수 / 2한 값을 저장합니다.
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
int n = rectangle.length;
for(int i = 0; i < n; i++) {
int x1 = rectangle[i][0] * 2;
int y1 = rectangle[i][1] * 2;
int x2 = rectangle[i][2] * 2;
int y2 = rectangle[i][3] * 2;
for(int p = x1; p <= x2; p++) {
for(int q = y1; q <= y2; q++) {
if(p == x1 || p == x2 || q == y1 || q == y2) {
if(map[p][q] == 0) {
map[p][q] = 1;
}
} else {
map[p][q] = 2;
}
}
}
}
bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
return answer;
}
- solution 메소드
- 모든 사각형(rectangle)을 테두리(1)와 내부(2)로 분류하여 map에 저장합니다.
- 좌표 확장
- 좌표를 *2하여 지도 상에서 모든 이동을 정수 단위로 표현합니다.
- BFS를 이용해 시작 위치에서 목표 위치까지 탐색합니다.
-