📖 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
💡 풀이 방식
• BFS
1. 범위를 2배로 늘려 0~100 으로 격자 크기를 늘린 2차원 int형 배열을 생성한다.
int[][] board = new int[101][101];
→ Why? 선이 아닌 좌표를 기준으로 하므로 크기를 2배로 확장해야 제대로 탐색을 할 수 있기 때문이다. (참고)
2. rectangle 배열을 돌며, 내부와 테두리를 구분해 위에서 만든 배열에 값을 저장해준다. (여기서도 2배해준 값 사용하기)
for(int[] r : rectangle) {
fill(2*r[0], 2*r[1], 2*r[2], 2*r[3]);
}
private static void fill(int x1, int y1, int x2, int y2) {
for(int i = x1 ; i <= x2 ; i++) {
for(int j = y1 ; j <= y2 ; j++) {
if(board[i][j] == 2) continue;
// 내부
board[i][j] = 2;
// 테두리값
if(i == x1 || i == x2 || j == y1 || j == y2)
board[i][j] = 1;
}
}
}
3. 캐릭터 위치부터 BFS 탐색을 통해 캐릭터 위치부터 각 좌표까지의 최소 이동거리를 계산한다. (좌표 간 최소 이동거리 계산)
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {sx, sy}); // [시작점] 캐릭터 위치
int[][] dist = new int[101][101]; // 방문 여부 & 이동 거리 저장용 배열 (0: 미방문)
dist[sx][sy] = 1; // 방문 처리 & 이동 거리 저장
while(!q.isEmpty()) {
int[] now = q.poll();
for(int d = 0 ; d < 4 ; d++) { //
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if(!inRange(nx, ny)) continue;
if(board[nx][ny] == 1 && dist[nx][ny] == 0) {
dist[nx][ny] = dist[now[0]][now[1]] + 1; // 방문 처리 & 이동 거리 갱신
q.add(new int[] {nx, ny});
}
}
}
4. 아이템 위치에서의 이동 거리를 2로 나눈 값을 정답으로 출력한다. (값을 2배 늘려줬으므로 원상복구)
answer = dist[ex][ey] / 2;
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
import java.util.*;
class Solution {
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int[][] board;
static int answer;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
board = new int[101][101]; // 격자 크기를 2배로 늘리기
for(int[] r : rectangle) {
fill(2*r[0], 2*r[1], 2*r[2], 2*r[3]);
}
bfs(2*characterX, 2*characterY, 2*itemX, 2*itemY);
return answer;
}
// 내부와 테두리 구분하는 메소드
private static void fill(int x1, int y1, int x2, int y2) {
for(int i = x1 ; i <= x2 ; i++) {
for(int j = y1 ; j <= y2 ; j++) {
if(board[i][j] == 2) continue;
board[i][j] = 2; // 내부
// 테두리값 구분하기
if(i == x1 || i == x2 || j == y1 || j == y2)
board[i][j] = 1;
}
}
}
private static void bfs(int sx, int sy, int ex, int ey) {
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {sx, sy});
int[][] dist = new int[101][101]; // 방문 여부 & 이동 거리 저장용 배열 (0: 미방문)
dist[sx][sy] = 1; // 방문 처리
while(!q.isEmpty()) {
int[] now = q.poll();
for(int d = 0 ; d < 4 ; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if(!inRange(nx, ny)) continue;
if(board[nx][ny] == 1 && dist[nx][ny] == 0) {
dist[nx][ny] = dist[now[0]][now[1]] + 1; // 방문 처리 & 이동 거리 갱신
q.add(new int[] {nx, ny});
}
}
}
answer = dist[ex][ey] / 2; // 격자 크기 2배 했으므로 2 나눠주기
}
private static boolean inRange(int x, int y) {
return (0 <= x && x <= 100 && 0 <= y && y <= 100);
}
}
|
cs |
➕ 다른 풀이 방식
- 내가 풀려고 했던 방식! 이동 횟수를 큐에 저장해서 푸는 방식.
그리고 테두리 구분하는 방식이 조금 다르다.
[프로그래머스] 위클리 챌린지 11주차 아이템 줍기 (Java)
#11주차 아이템 줍기 유형 : 구현 / 그래프 탐색 코딩테스트 연습 - 아이템 줍기 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 pro
loosie.tistory.com
💦 어려웠던 점
- 이동 횟수를 큐에 저장해서 하려고 생각했었다. (이 방법으로도 해결할 수 있긴 하다.)
- 격자 크기를 2배로 늘릴 생각을 하지 못 했다.
🧐 새로 알게 된 내용
- 격자 크기를 2배로 늘려야 하는 이유
- 테두리 필터링 방식!!
private static void fill(int x1, int y1, int x2, int y2) {
for(int i = x1 ; i <= x2 ; i++) {
for(int j = y1 ; j <= y2 ; j++) {
if(board[i][j] == 2) continue;
board[i][j] = 2; // 내부
// 테두리값 구분하기
if(i == x1 || i == x2 || j == y1 || j == y2)
board[i][j] = 1;
}
}
}
- 이동 횟수를 큐에 저장하기 vs 이동 거리 배열에 값 저장하기... 그냥 찾아봤다
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
[프로그래머스] 아이템 줍기(java)
https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는
kimtaesoo99.tistory.com
'코테 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/Level3] 경주로 건설 (JAVA) (0) | 2024.05.14 |
---|---|
[프로그래머스/Level3] 불량 사용자 (JAVA) (0) | 2024.05.13 |
[프로그래머스/Level2] [3차] 방금그곡 (JAVA) (0) | 2024.04.11 |
[프로그래머스/Level2] 숫자 블록 (JAVA) (0) | 2024.04.11 |
[프로그래머스/Level2] 후보키 (JAVA) (0) | 2024.04.08 |