DFS/BFS는 이제 웬만해선 잘 푼다고 생각했는데, 하나 더 배우게 됐다.
import java.util.*;
class Solution {
static class player
{
int x;
int y;
int move;
public player(int y, int x, int move)
{
this.x = x;
this.y = y;
this.move = move;
}
}
static int[][] map = new int[51][51];
static boolean[][] visit = new boolean[51][51];
static Queue<player> q;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int answer = Integer.MAX_VALUE;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
q = new LinkedList<>();
q.add(new player(characterY, characterX, 0)); //건들지마
for(int i = 0 ; i < rectangle.length ; i++)
{
int lx = rectangle[i][0];
int ly = rectangle[i][1];
int rx = rectangle[i][2];
int ry = rectangle[i][3];
for(int j = ry ; j >= ly ; j--)
{
for(int k = rx ; k >= lx ; k--)
{
if(map[j][k] == 2) continue;
map[j][k] = 2;
if(j == ly || j == ry || k == lx || k == rx)
map[j][k] = 1;
}
}
}
for(int i = 0 ; i <= 50 ; i++)
{
for(int j = 0 ; j <= 50 ; j++)
{
if(map[i][j] >= 1)
{
if(i == characterY && j == characterX)
System.out.print(map[i][j]+"*");
else if(i == itemY && j == itemX)
System.out.print(map[i][j]+"$");
else
System.out.print(map[i][j]+" ");
}
else System.out.print(" ");
}
System.out.println();
}
bfs(itemY, itemX);
return answer;
}
public static void bfs(int iy, int ix)
{
while(!q.isEmpty())
{
player p = q.poll();
if(p.y == iy && p.x == ix)
{
answer = Math.min(answer, p.move);
return;
}
if(visit[p.y][p.x]) continue;
visit[p.y][p.x] = true;
for(int i = 0 ; i < 4 ; i++)
{
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if(nx < 0 || ny < 0 || nx > 50 || ny > 50) continue;
if(!visit[ny][nx] && map[ny][nx] == 1)
q.add(new player(ny, nx, p.move+1));
}
}
}
}첫 코드는 이렇게 작성했는데
1 1 1 1 1 1 1
1 2 2 2 2 2 1
1*2 2 2 2 2 1
1 1 1 2 2 1 1
1 1 2 1 //이 부분 5,3
1 1 1 2 1 1 1 //이 부분 6,3이 문제
1 2 2 2 2 2 1
1 1 1 2 1 1$1
1 1 1저기 주석으로 표시한 부분은 그림 상 떨어져 있는 부분이지만, for문을 통해 그리게 되면 붙어있는 것으로 되어버린다.
도대체 저 부분을 어떻게 해결할지 고민을 하던 와중 내가 참고한 블로그에서 풀이방법을 봤는데, 솔직히 처음 봤을 때 작성자와 다른 것이 무엇인가 고민을 많이 했다.
그러다 작성자가 map의 크기를 50까지가 아닌 100까지로 하고 전체적으로 2배로 늘린 것을 발견했는데 설마 이것 때문인가 반신반의하면서 늘려봤는데
1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2 2 2 1
1 2 2 2 2 2 2 2 2 2 2 2 1
1 2 2 2 2 2 2 2 2 2 2 2 1
1*2 2 2 2 2 2 2 2 2 2 2 1
1 2 2 2 2 2 2 2 2 2 2 2 1
1 1 1 1 1 2 2 2 2 2 1 1 1
1 2 2 2 2 2 1
1 1 1 2 2 2 1
1 2 2 2 1
1 1 1 1 1 2 2 2 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2 2 2 1
1 2 2 2 2 2 2 2 2 2 2 2 1
1 2 2 2 2 2 2 2 2 2 2 2 1
1 1 1 1 1 2 2 2 1 1 1$1 1
1 2 2 2 1
1 1 1 1 1시원하게 사이가 벌어졌다. 거리도 2배로 늘어났기 때문에 2로 나눠주면 된다...
백준을 자주 풀다 보니 map을 표시하는 이런 센스도 죽은 듯싶다...
<문제>
https://school.programmers.co.kr/learn/courses/30/lessons/87694
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
<소스코드>
import java.util.*;
class Solution {
static class player
{
int x;
int y;
int move;
public player(int y, int x, int move)
{
this.x = x;
this.y = y;
this.move = move;
}
}
static int[][] map = new int[101][101];
static boolean[][] visit = new boolean[101][101];
static Queue<player> q;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int answer = Integer.MAX_VALUE;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
q = new LinkedList<>();
q.add(new player(2*characterY, 2*characterX, 0)); //건들지마
for(int i = 0 ; i < rectangle.length ; i++)
{
int lx = rectangle[i][0]*2;
int ly = rectangle[i][1]*2;
int rx = rectangle[i][2]*2;
int ry = rectangle[i][3]*2;
for(int j = ry ; j >= ly ; j--)
{
for(int k = rx ; k >= lx ; k--)
{
if(map[j][k] == 2) continue;
map[j][k] = 2;
if(j == ly || j == ry || k == lx || k == rx)
map[j][k] = 1;
}
}
}
bfs(2*itemY, 2*itemX);
return answer/2;
}
public static void bfs(int iy, int ix)
{
while(!q.isEmpty())
{
player p = q.poll();
if(p.y == iy && p.x == ix)
{
answer = Math.min(answer, p.move);
return;
}
if(visit[p.y][p.x] || map[p.y][p.x] != 1) continue;
visit[p.y][p.x] = true;
for(int i = 0 ; i < 4 ; i++)
{
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if(nx < 0 || ny < 0 || nx > 100 || ny > 100) continue;
q.add(new player(ny, nx, p.move+1));
}
}
}
}<참고>
[프로그래머스]level 3: 아이템 줍기_Java(위클리 11주차)
[문제 설명] 다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다. 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘
arinnh.tistory.com
'프로그래머스 > Level 3' 카테고리의 다른 글
| 프로그래머스(Lv.3) - [1차] 셔틀버스(Java) (카카오) (0) | 2024.01.17 |
|---|---|
| 프로그래머스(Lv.3) - 부대복귀(Java) (다익스트라) (0) | 2023.12.18 |
| 프로그래머스(Lv.3) - 여행경로(Java) (0) | 2023.08.14 |
| 프로그래머스(Lv.3) - 다단계 칫솔 판매(Java) (0) | 2023.08.14 |
| Lv.3 이중우선순위큐 (0) | 2023.07.09 |