https://school.programmers.co.kr/learn/courses/30/lessons/87694
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1) 풀이
며칠동안 푼 문제,,,,, 진짜 개에바임 🥹
사실 처음 문제 보고 bfs 로 그냥 풀면 되겠다 싶어서 쉽게 풀릴줄 알았는데
생각보다 오래 걸려서 맘고생을 좀 했다
처음에는 이 방법으로 했다
1. 50x50 board, visitied 각각의 2차원 배열을 생성
2. 그냥 말그대로 중첩 for 문 돌면서 모든 도형 1로 board 배열에 찍기
3. board 를 순회해서, 1로 되어있는 칸 중심으로 8칸(칸 중심으로 9칸 모양이나, 본인은 제외) 둘러보고 하나라도 0인 값 있으면 2로 바꿔줌 (하나라도 0인 값이 있으면 여기가 제일 테두리라는 의미이기 때문)
4. 캐릭터 위치를 queue 제일 처음에 넣어주고, 아이템 위치가 0일 동안 while 문으로 bfs 돌리면서 visited 에 거리 측정(true/false 가 아니라 현재 위치에서 1씩 더해서 거리 구해주기)
이런식으로 구해줬는데 주어진 테케는 다 맞는데 막상 정답 채점 돌리면 몇개가 오답이길래
질문하기에 있는 반례라는 케이스들을 돌려보니까 자꾸 2씩 부족했다..!
전부 정답에서 2씩 모자라는 것으로 보아, 알고리즘 자체는 맞는데 똑같은 부분에서 자꾸 빠트리고 가는 느낌이었다
사실 위의 순서대로 했을 때, 테두리는 똑바로 구해주는 것 같은데 뭐가 문제인지 파악하지 못하고 있다가
질문하기를 보니까 죄다 좌표를 2씩 곱해야한다고 설명하고 있었다
모태 문과인 나는.. 도대체 왜 2씩 곱해줘야 하는지가 이해가 안 갔다 도대체 왜??
그러다가 나같은 바부😓도 알아먹을 수 있게 설명을 써놓은 어떤 블로그를 보게 되었다 (혹시 보신다면 정말 감사합니다..)
bfs의 특성상, 테두리를 다 거친 제일 빠른 루트가 아닌, 테두리더라도 몇개 칸을 임의로 생략한 빠른 루트로 가기 때문에 값이 모자라게 나오는 것이었다..!
저기에 좌표에 2를 곱해야하는 이유를 바아로 납득하고 돌려준 결과.. 바로 정답!
정말 허무한.. 하지만 많은 것을 배운 문제였던 걸로 ㅋㅎ..
나 이제 레벨 3도 푼다..!
2) 최종 소스코드
function solution(rectangle, characterX, characterY, itemX, itemY) {
const dx=[-1,0,1,-1,1,-1,0,1];
const dy=[1,1,1,0,0,-1,-1,-1];
let board=Array.from(new Array(102),()=>Array(102).fill(0));
const visited=Array.from(new Array(102),()=>Array(102).fill(0));
rectangle=rectangle.map((v)=>v.map((e)=>e*2));
for(let i=0;i<rectangle.length;i++){
let leftx=rectangle[i][0];
let lefty=rectangle[i][1];
let rightx=rectangle[i][2];
let righty=rectangle[i][3];
for(let k=lefty;k<=righty;k++){
for(let j=leftx;j<=rightx;j++){
if(board[k][j]===1) continue;
board[k][j]=1;
}
}
}
for(let i=0;i<board.length;i++){
for(let k=0;k<board[i].length;k++){
if(board[i][k]===0) continue;
for(let j=0;j<8;j++){
let cury=i+dy[j];
let curx=k+dx[j];
if(cury<0||cury>=board.length||curx<0||curx>=board.length) continue;
if(board[cury][curx]===0){
board[i][k]=2;
break;
}
}
}
}
const cx=[0,1,0,-1];
const cy=[1,0,-1,0];
let answer = 0;
const queue=[];
queue.push([characterY*2,characterX*2]);
while(visited[itemY*2][itemX*2]===0){
let cur=queue.shift();
for(let i=0;i<4;i++){
let dy=cur[0]+cy[i];
let dx=cur[1]+cx[i];
if(visited[dy][dx]!==0||board[dy][dx]!==2) continue;
if(dy<0||dy>=board.length||dx<0||dx>=board.length) continue;
visited[dy][dx]=visited[cur[0]][cur[1]]+1;
queue.push([dy,dx]);
}
}
return visited[itemY*2][itemX*2]/2;
}3) 참고자료
[프로그래머스] 아이템 줍기
직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧
velog.io
'Problem Solving > 프로그래머스' 카테고리의 다른 글
| [프로그래머스/JavaScript] 숫자 변환하기 (0) | 2023.05.18 |
|---|---|
| [프로그래머스/JavaScript] 최고의 집합 (0) | 2023.04.06 |
| [프로그래머스/JavaScript] 소수 찾기 (1) | 2022.12.15 |
| [프로그래머스/JavaScript] 최소직사각형 (0) | 2022.12.14 |
| [프로그래머스/JavaScript] 베스트앨범 (0) | 2022.12.14 |