오늘의 코테 문제!
아이디어를 생각했어야만 했던 문제!!
아이템 줍기](https://school.programmers.co.kr/learn/courses/30/lessons/87694)
단순한 BFS문제라고 생각했으나 아니었음 ㅋ
우선 문제를 해결하기 위해 나는
그래프를 컴퓨터가 알아볼 수 있는 형식으로 그려야한다고 생각했다.
import java.util.*;
class Solution {
static int[][] board;
static int[] dx = {1, -1, 0, 0}; // 상하좌우
static int[] dy = {0, 0, 1, -1}; // 상하좌우
static boolean[][] visited;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
// board 크기는 101x101로 충분히 크게 설정
board = new int[55][55];
visited = new boolean[55][55];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0];
int y1 = rec[1];
int x2 = rec[2];
int y2 = rec[3];
//x축 채우기
//위의 방법을 사용하면 말 그대로 사각형의 안쪽만 비어있게 된다.
//둘이 겹쳐지게 된다면 이 방법은 사용할 수 없음
//1로채우기
// for(int x = x1; x<=x2; x++){
// for(int y =y1; y<y2; y++){
// board[x][y] =1;
// }
// }
// //0으로 테두리만 남기기
// for(int x = x1+1; x<x2; x++){
// for(int y =y1+1; y<y2-1; y++){
// board[x][y] =0;
// }
//테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
for(int i=0; i<13; i++){
for(int k=0; k<13; k++){
System.out.print(board[i][k]+ " ");
}
System.out.println();
}
return 0;
}
}
첫 시도
처음에는 범위내에 있는 모든 값을 1로 채우고 안에 있는 것을 0으로 바꿔주는 방식으로 선택했다.
박스가 하나인 경우는 내가 원하는대로 잘 나오는 것을 확인할 수 있었다
하지만 여러개일땐 달랐다 엉어엉엉엉
두 번째 시도 테두리만 그려보기
import java.util.*;
class Solution {
static int[][] board;
static int[] dx = {1, -1, 0, 0}; // 상하좌우
static int[] dy = {0, 0, 1, -1}; // 상하좌우
static boolean[][] visited;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
// board 크기는 101x101로 충분히 크게 설정
board = new int[55][55];
visited = new boolean[55][55];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0];
int y1 = rec[1];
int x2 = rec[2];
int y2 = rec[3];
//x축 채우기
// //테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
for(int i=0; i<13; i++){
for(int k=0; k<13; k++){
System.out.print(board[i][k]+ " ");
}
System.out.println();
}
return 0;
}
}
이제 테두리가 겹치는부분을 0으로 메꿔야한다...
위 방식들의 문제점
사실 위 방식들이 모두 추구하는 것은 똑같다.
내가 원하는 도표로 그리는 것
하지만 한 가지 문제점이 있는데
이렇게 표현할 수 없는 경우이다.
좀 더 자세하게 표현하자면
내가 원하는 그래프 모양으로 만드려면 어떻게 해야할까?
저런식으로 표현되면 우리가 원하는 답을 잘 얻을 수 없다. 그럼 어떻게 표현해야 할까?
왼쪽은 원래 원하는 경로이고 오른쪽은 아니다!!!
해결안1. 그래프를 키워보기
왼쪽의 그래프를 2배로 변경하면 오른쪽처럼 된다.
그러면 ㄷ자 커브도 처리할 수 있게 된다!
board = new int[55][55];
visited = new boolean[55][55];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0]*2;
int y1 = rec[1]*2;
int x2 = rec[2]*2;
int y2 = rec[3]*2;
//x축 채우기
// //테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
for (int i = x1 + 1; i < x2; i++) {
for (int j = y1 + 1; j < y2; j++) {
board[i][j] = 0; // 내부 비우기
}
}테두리를 만드는 로직이다.
내부를 위처럼 비우면 아래와 같은 현상이 발생한다. 우리는 테두리를 제외하고 전부다 뺄 예정이니까
// board 크기는 101x101로 충분히 크게 설정
board = new int[55][55];
visited = new boolean[55][55];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0]*2;
int y1 = rec[1]*2;
int x2 = rec[2]*2;
int y2 = rec[3]*2;
//x축 채우기
// //테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
// 내부 채우기 방지: 경계 내부의 좌표를 0으로 유지
for (int[] rec : rectangle) {
int x1 = rec[0] * 2;
int y1 = rec[1] * 2;
int x2 = rec[2] * 2;
int y2 = rec[3] * 2;
for (int i = x1 + 1; i < x2; i++) {
for (int j = y1 + 1; j < y2; j++) {
board[i][j] = 0; // 내부 비우기
}
}
}이렇게 표시하는게 끝나고 내부를 비워주면 된다.
왜 for을 저렇게 도는지는 위의 그림을 보면 된다.
그래프 테두리 탐색하기
테두리는 시작접에서 bfs를 돌아주면 되는데 이때 테두리인 부분(1로 설정된 부분)만 돌면서 item의 위치에 도달하면 답을 리턴하면된다. 이건 하도 많이 풀어봤으니 패스
private static int bfs(int startX, int startY, int itemX, int itemY){
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{startX, startY,0});
visited[startX][startY] =true;
while(!queue.isEmpty()){
int[] cur =queue.poll();
int x = cur[0];
int y = cur[1];
int dist = cur[2];
for(int dir =0; dir<4; dir++){
int nx = x + dx[dir];
int ny = y +dy[dir];
if(nx<0 || ny <0 || nx>=101|| ny>=101)continue;
if(itemX==x && y ==itemY){
return (dist+1)/2;
}
if(board[nx][ny] ==1 && !visited[nx][ny]){
visited[nx][ny] =true;
queue.add(new int[]{nx,ny,dist+1});
}
}
}
return -1;
}
참고로 전해지는 인자는 모두 *2 가 된 상태에서 보내야한다.!!
최종 코드
import java.util.*;
class Solution {
static int[][] board;
static int[] dx = {1, -1, 0, 0}; // 상하좌우
static int[] dy = {0, 0, 1, -1}; // 상하좌우
static boolean[][] visited;
private static int bfs(int startX, int startY, int itemX, int itemY){
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{startX, startY,0});
visited[startX][startY] =true;
while(!queue.isEmpty()){
int[] cur =queue.poll();
int x = cur[0];
int y = cur[1];
int dist = cur[2];
for(int dir =0; dir<4; dir++){
int nx = x + dx[dir];
int ny = y +dy[dir];
if(nx<0 || ny <0 || nx>=101|| ny>=101)continue;
if(itemX==x && y ==itemY){
return (dist+1)/2;
}
if(board[nx][ny] ==1 && !visited[nx][ny]){
visited[nx][ny] =true;
queue.add(new int[]{nx,ny,dist+1});
}
}
}
return -1;
}
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
// board 크기는 101x101로 충분히 크게 설정
board = new int[101][101];
visited = new boolean[101][101];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0]*2;
int y1 = rec[1]*2;
int x2 = rec[2]*2;
int y2 = rec[3]*2;
//x축 채우기
// //테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
// 내부 채우기 방지: 경계 내부의 좌표를 0으로 유지
for (int[] rec : rectangle) {
int x1 = rec[0] * 2;
int y1 = rec[1] * 2;
int x2 = rec[2] * 2;
int y2 = rec[3] * 2;
for (int i = x1 + 1; i < x2; i++) {
for (int j = y1 + 1; j < y2; j++) {
board[i][j] = 0; // 내부 비우기
}
}
}
// BFS를 통해 최단 거리 계산
return bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
}
}
REVIEW
아이디어를 짜내는게 어려웠던 문제!
예전에 벌집모양 BFS를 풀었던 기억이 새록새로 떠오른다.(겉에 두껍게 2겹을 감싸서 테두리를 구하는 방법, 한 칸을 기준으로 바깥과 연결된 부분, 안쪽과 연결된 부분을 구해서, 테두리를 카운트하는 방법)
뭐 이런저런 방법들을 하나씩 알아가고있다.
복습이 얼마나 중요한지 좀 느끼게 된 계기?
클럽장님이 알려주신 꿀팁
보통 횟수를 카운트 할 떄
for(int i=0; i<어쩌구 반복문 조건)
for(int 저쩌구 반복문 조건){
if(여기로 오게될 어떠한 조건){
bfs수행!
하고 이곳에서 카운트가 이루어진다.
}
}
보통 bfs를 여러번 돌려야하는 경우? 위와 같은 방법을 사용한다. 동 떨어진곳에 시작점이 있는 경우
이건 아닌데 완전 잘못된 예시를 꺼내버렸다.
뭐 아무튼
다시 말하자면
bfs를 돌 때 수행시간, 거리를 구하는 방법
8/22 자바 챌린저
import java.util.*;
class Solution {
private int[] dy = {1, 0, -1, 0};
private int[] dx = {0, 1, 0, -1};
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
var q = new LinkedList<Pos>();
var map = new int[101][101];
var visited = new int[101][101];
for (int i = 0; i < rectangle.length; i++) {
var rect = rectangle[i];
var num = 1 << i;
var leftX = rect[0] * 2;
var leftY = rect[1] * 2;
var rightX = rect[2] * 2;
var rightY = rect[3] * 2;
for (int y = leftY; y <= rightY; y++) {
for (int x = leftX; x <= rightX; x++) {
map[y][x] += num;
}
}
}
var dist = 0;
visited[characterY * 2][characterX * 2] = 1;
q.add(new Pos(characterY * 2, characterX * 2));
//여기를 잘 보렴
// 단위 시간 혹은 단위 거리 만큼만 BFS 돌리는 방법
while(!q.isEmpty()) {
//큐 사이즈 만큼 뽑아부기
var size = q.size();
//그 사이즈만큼 돌리기!!!! 단위가 되는거임
while(size-- > 0) {
var cur = q.poll();
if (cur.y == itemY * 2 && cur.x == itemX * 2) {
return dist / 2;
}
for (int dir = 0; dir < 4; dir++) {
var ny = cur.y + dy[dir];
var nx = cur.x + dx[dir];
if (ny < 0 || ny > 100 || nx < 0 || nx > 100) {
continue;
}
if (visited[ny][nx] == 1) {
continue;
}
if (map[ny][nx] == 0) {
continue;
}
if (isInside(ny, nx, map[ny][nx], rectangle)) {
continue;
}
visited[ny][nx] = 1;
q.add(new Pos(ny, nx));
}
}
dist++;
}
return dist;
}
// bitmasking 을 이용한 내부 여부 확인
private boolean isInside(int y, int x, int number, int[][] rectangle) {
for (int i = 0; i < rectangle.length; i++) {
if ((number & 1 << i) == 0) {
continue;
}
var leftX = rectangle[i][0] * 2;
var leftY = rectangle[i][1] * 2;
var rightX = rectangle[i][2] * 2;
var rightY = rectangle[i][3] * 2;
if (leftY < y && y < rightY && leftX < x && x < rightX) {
return true;
}
}
return false;
}
private static class Pos {
int y;
int x;
private Pos(int y, int x) {
this.y = y;
this.x = x;
}
}
}
핵심이 되는 부분은
//여기를 잘 보렴
// 단위 시간 혹은 단위 거리 만큼만 BFS 돌리는 방법
while(!q.isEmpty()) {
//큐 사이즈 만큼 뽑아부기
var size = q.size();
//그 사이즈만큼 돌리기!!!! 단위가 되는거임
while(size-- > 0) {
var cur = q.poll();
if (cur.y == itemY * 2 && cur.x == itemX * 2) {
return dist / 2;
}
for (int dir = 0; dir < 4; dir++) {윤지원 클럽장님이 알려주신 BFS단위 측정하는 방법
//여기를 잘 보렴
// 단위 시간 혹은 단위 거리 만큼만 BFS 돌리는 방법
while(!q.isEmpty()) {
//큐 사이즈 만큼 뽑아부기
var size = q.size();
//그 사이즈만큼 돌리기!!!! 단위가 되는거임
while(size-- > 0) {
var cur = q.poll();
... 아랫 부분은 우리가 잘 아는 통상적인 BFS로직
이런 느낌? q의 사이즈 만큼 반복하면 단위 단으로 반복할 수 있다.
신박한 BFS문제들
최근 풀고있는 BFS, DFS문제들은 단순히 BFS를 쓰는 것이 아니라 아이디어를 활용하는 문제가 나오는 듯 하다. 이번에 2배로 늘려버리는 것도 그렇고
비슷한 BFS문제를 찾아봤따.
토마토
중간맛 문제. 조금만 생각하면 잘 풀 수 있는 문제이다. bfs에 조금 익숙해진 분들이 도전하면 좋을 맛 토맡토 맛있는 토맡토
백준 불
불 이라는 문제이다. 불과 지훈이가 어떤 지점에서 어떤 조건으로 만나는지 잘 생각해보자
벽 부수고 이동하기
지금도 이 문제를 제대로 풀 자신이 없다. 새로운 조건이 추가되었는데 잘 생각해보자 어떤 미션을 수행할지 안할지를 그리고 그걸 어떤 조건으로 줘야하는지
참고로 벽 부수는건 시리즈로 있는데 난 이거 한 문제만 풀어봤다.
일루미네이션 백준
이미 스터디때 풀어봤지만 이것도 이런거 저런거 생각해야 했어서 꽤 신박했던 문제이다. 이걸 푼 기억이 있기 때문에 오늘 문제를 잘 이해한거 아닌가 싶다.
REVIEW
복습이 얼마나 중요한지 다시 한 번... 되새깁니다...
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
Yellta가 BE개발해요! 왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜 가 제일 중요하죠