문제
문제 설명 펼쳐보기
문제 설명
다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.
지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.
만약 직사각형을 겹친 후 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.
단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.
즉, 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.
지형이 2개 이상으로 분리된 경우도 없습니다.
한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.
지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.
제한사항
rectangle의 세로(행) 길이는 1 이상 4 이하입니다.rectangle의 원소는 각 직사각형의[좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y]좌표 형태입니다.- 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
- 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
- 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
characterX,characterY는 1 이상 50 이하인 자연수입니다. 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.itemX,itemY는 1 이상 50 이하인 자연수입니다. 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.- 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.
- 전체 배점의 50%는 직사각형이 1개인 경우입니다.
- 전체 배점의 25%는 직사각형이 2개인 경우입니다.
- 전체 배점의 25%는 직사각형이 3개 또는 4개인 경우입니다.
입출력 예
| rectangle | characterX | characterY | itemX | itemY | result |
|---|---|---|---|---|---|
[[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 |
[[1,1,5,7]] |
1 | 1 | 4 | 7 | 9 |
[[2,1,7,5],[6,4,10,10]] |
3 | 1 | 7 | 10 | 15 |
[[2,2,5,5],[1,3,6,4],[3,1,4,6]] |
1 | 4 | 6 | 3 | 10 |
입출력 예 설명
입출력 예 #1
캐릭터 위치는 (1, 3)이며, 아이템 위치는 (7, 8)입니다. 굵은 선을 따라 이동하는 경로가 가장 짧습니다.
입출력 예 #2
캐릭터 위치는 (9, 7)이며, 아이템 위치는 (6, 1)입니다. 굵은 선을 따라 이동하는 경로가 가장 짧습니다.
입출력 예 #3
캐릭터 위치는 (1, 1)이며, 아이템 위치는 (4, 7)입니다. 굵은 선을 따라 이동하는 경로가 가장 짧습니다.
문제 요약
여러 직사각형을 겹쳐 만든 도형의 둘레만을 따라 이동할 수 있을 때, 캐릭터에서 아이템까지의 최단 이동 거리를 구하는 문제다.
핵심은 "둘레"를 코드로 어떻게 판별하고, 그 위에서 최단 거리를 어떻게 구할 것인가다.
풀이 원리
BFS로 최단 거리를 구한다는 방향은 자연스럽다.
문제는 "이 칸이 둘레에 해당하는가"를 어떻게 판정하느냐다.
이 문제를 검색하면 거의 항상 나오는 풀이가 있다.
모든 좌표를 2배로 늘린 격자를 만들고, 사각형 내부를 칠한 다음,
칠해진 칸 중에 "빈 칸과 맞닿은 칸"을 테두리로 표시해서 그 위에서 BFS를 돌리면 된다.
그럴듯해 보여서 그대로 짜봤다.
// 1. 좌표를 2배로 늘려서 사각형 내부(경계 포함)를 채운다
const board = Array.from({ length: 102 }, () => new Array(102).fill(0));
for (const [x1, y1, x2, y2] of rectangle) {
for (let x = x1 * 2; x <= x2 * 2; x++) {
for (let y = y1 * 2; y <= y2 * 2; y++) {
board[x][y] = 1;
}
}
}
// 2. 채워진 칸 중 빈 칸과 맞닿은 칸을 테두리(2)로 표시
for (let x = 0; x < 102; x++) {
for (let y = 0; y < 102; y++) {
if (board[x][y] !== 1) continue;
for (const [dx, dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
const nx = x + dx, ny = y + dy;
if (board[nx]?.[ny] === 0) { board[x][y] = 2; break; }
}
}
}
// 이후 테두리(2) 위에서 BFS...돌려봤더니 직사각형이 1개인 예제만 통과하고 나머지는 전부 실패했다.
뭐가 문제인지 직접 그려서 확인해봤다.
예제 1번 지형을 2배 격자에 그려보면 (# = 테두리로 판정된 칸)
#####
#...#
####.....####
#...........#
#...........#
#...........#
####.....####
#...#
##....#
#.....#
####.......##
#...........#
#...........#
#...........#
#...........#
#...........#
#############그림만 보면 테두리가 한 줄로 잘 이어진 것처럼 보인다.
그런데 이 # 칸들을 상하좌우(4방향)로만 연결해서 연결 요소를 세어보면 결과가 이렇다.
전체 테두리 칸 개수: 65
시작점에서 4방향으로 연결된 칸 개수: 29
전체 연결 요소 개수: 765개 중 29개만 연결되고, 나머지는 7개의 조각으로 쪼개져 있었다.
(8, 11) 같은 좌표는 위/아래/왼쪽/오른쪽 어디를 봐도 테두리 칸이 없는 고립된 섬이었다.
이유는 이랬다.
좌표를 2배로 늘리는 과정에서 각 칸을 for (x = x1*2; x <= x2*2; x++)처럼 그대로 2배 확대해서 채웠기 때문에, 도형의 모양(위상)이 원래 1배 격자와 완전히 똑같았다.
사진을 200% 확대한 것과 다를 게 없다.
오목하게 들어간 부분(잘록한 목 부분)에서 테두리 칸들이 대각선으로만 맞닿는 지점은, 1배든 2배든 축척만 다를 뿐 똑같이 존재한다.
이 현상은 이미지 처리에서 유명한 4-연결성 vs 8-연결성 문제다.
픽셀 격자 위에서 대각선으로 이어지는 경계선은 사람 눈에는 자연스럽게 이어져 보이지만(8-연결), 상하좌우로만 움직이면 끊어진다(4-연결).
칠해진 두 영역이 대각선으로만 만나는 지점 (○ = 빈칸, ■ = 채워진칸)
○ ■
■ ○"빈칸과 맞닿은 칸은 테두리다"라는 판정 자체는 틀리지 않았다.
문제는 그렇게 판정된 테두리 칸들이 4방향으로 서로 이어져 있다는 보장이 없다는 것이고, 이 끊김은 격자를 몇 배로 늘리든 스케일만 다를 뿐 똑같이 발생한다.
그래서 관점을 완전히 바꿔야 한다.
색칠 공부를 떠올려보면 쉽다.
도화지 위에 직사각형 몇 개를 겹쳐서 색칠했다고 하면, 도형의 "테두리"란 색칠된 부분과 안 된 부분이 맞닿는 경계선이다.
캐릭터가 걷는 길은 바로 이 경계선이지, 색칠된 칸 자체가 아니다.
즉 캐릭터는 칸 위를 걷는 게 아니라 칸과 칸 사이의 선 위를 걷는다.
이 관점을 코드로 옮기면 두 단계로 나뉜다.
- 도화지의 모든 1×1 칸에 대해 "색칠됐는가(=어떤 직사각형이든 그 칸을 덮고 있는가)"만
true/false로 기록한다. - 그을 수 있는 모든 가로선/세로선 하나하나에 대해 물어본다: "이 선을 사이에 둔 양쪽 칸의 색칠 여부가 다른가?" 다르면 그 선은 분명 경계선이니 "걸을 수 있는 길"로 등록하고, 같으면(둘 다 색칠됐거나 둘 다 안 됐거나) 그냥 무시한다.
위쪽 칸 색칠됨 ███████
──────────────────────── ← 경계! 걸을 수 있음 (위는 색칠, 아래는 안 됨)
아래쪽 칸 색칠 안 됨핵심 아이디어를 한 문장으로 요약하면 이렇다.
어떤 단위 변을 사이에 두고 있는 두 칸 중, 한쪽만 도형 내부이고 다른 한쪽은 바깥이라면
그 변은 반드시 둘레의 일부다.
이렇게 판정된 "걸을 수 있는 선"들만 모으면 서로 이어진 길의 네트워크, 즉 미로가 만들어진다.
그리고 여기서 중요한 건, 이 방식은 "칸"이 아니라 "선"과 "선이 만나는 점"으로 그래프를 만들기 때문에 대각선으로만 이어져서 끊기는 문제 자체가 애초에 성립할 여지가 없다는 점이다.
두 직사각형이 만나는 지점은 그냥 여러 선이 모이는 교차로가 될 뿐이다.
이 길의 네트워크가 완성되고 나면 나머지는 익숙한 문제다.
캐릭터 위치에서 출발해 한 걸음씩 사방으로 퍼져나가다가 아이템 위치에 닿을 때까지 걸음 수를 세는, 흔한 미로 최단거리 BFS일 뿐이다.
결국 이 문제가 어려워 보이는 이유는 BFS 자체가 아니라 "걸을 수 있는 길이 정확히 무엇인지"를 미리 정의하는 부분에 있고, 그 부분을 색칠하기 → 경계선 찾기 → 미로 찾기 세 단계로 쪼개고 나면 나머지는 다 익숙한 조각들이다.
처음 시도한 코드와 문제점
function solution(rectangle, characterX, characterY, itemX, itemY) {
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let move = 0;
const visited = Array.from({ length: maxX }, () => new Array(maxY).fill(false));
const queue = [[characterX, characterY]];
visited[characterX][characterY] = true;
while (queue.length > 0) {
const [x, y] = queue.pop();
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
if (nx === itemX && ny === itemY) break;
if (visited[nx][ny]) continue;
for (const [lbx, lby, rtx, rty] of rectangle) {
if ((lby <= y <= rty && (lbx === x || x === rtx))
|| (lbx <= x <= rtx && (lby === y || y === rty))) {
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
}
return move;
}BFS로 풀겠다는 방향 자체는 맞았지만 실행 디테일에서 세 가지가 어긋나 있었다.
move를 선언만 해놓고 한 번도 증가시키지 않는다. 무조건 0을 반환한다.queue.pop()은 배열 맨 뒤에서 꺼내는 거라 스택이다. BFS가 아니라 DFS로 동작하고 있었다. 최단 거리를 구하려면 앞에서 꺼내는 진짜 BFS여야 한다.- "둘레인지 판별하는 로직"에서 검사 대상이 뒤바뀌어 있다. 반복문 안에서
x, y(지금 서 있는 칸)가 둘레인지를 검사하고 있는데, 정작 그 판정 결과로visited와queue에 넣는 건nx, ny(다음 칸)다. 게다가lby <= y <= rty같은 비교는 JS에서(lby <= y) <= rty로 왼쪽부터 계산되기 때문에 boolean과 숫자를 비교하는 전혀 다른 식이 되어버린다.
최종 코드
function solution(rectangle, characterX, characterY, itemX, itemY) {
const N = 51; // 좌표는 1~50이므로 넉넉히 0~50
// cellFilled[x][y] : 단위 정사각형 [x,x+1] x [y,y+1] 이 사각형들의 합집합 내부에 있는지
const cellFilled = Array.from({ length: N }, () => new Array(N).fill(false));
for (const [x1, y1, x2, y2] of rectangle) {
for (let x = x1; x < x2; x++) {
for (let y = y1; y < y2; y++) {
cellFilled[x][y] = true;
}
}
}
const filled = (x, y) =>
(x >= 0 && y >= 0 && x < N && y < N) ? cellFilled[x][y] : false;
// 격자점(x,y) 사이의 변이 "경계"인지 확인해서 인접 리스트 구성
const key = (x, y) => x * 60 + y;
const adj = new Map();
const addEdge = (x1, y1, x2, y2) => {
const k1 = key(x1, y1), k2 = key(x2, y2);
if (!adj.has(k1)) adj.set(k1, []);
if (!adj.has(k2)) adj.set(k2, []);
adj.get(k1).push(k2);
adj.get(k2).push(k1);
};
for (let x = 0; x < N; x++) {
for (let y = 0; y < N; y++) {
// 가로변 (x,y)-(x+1,y) : 위쪽 셀 (x,y), 아래쪽 셀 (x,y-1)
if (x < N-1) {
const above = filled(x, y);
const below = filled(x, y - 1);
if (above !== below) addEdge(x, y, x + 1, y);
}
// 세로변 (x,y)-(x,y+1) : 오른쪽 셀 (x,y), 왼쪽 셀 (x-1,y)
if (y < N-1) {
const right = filled(x, y);
const left = filled(x - 1, y);
if (right !== left) addEdge(x, y, x, y + 1);
}
}
}
// BFS
const startKey = key(characterX, characterY);
const endKey = key(itemX, itemY);
const dist = new Map();
dist.set(startKey, 0);
const queue = [startKey];
let head = 0;
while (head < queue.length) {
const cur = queue[head++];
if (cur === endKey) return dist.get(cur);
const neighbors = adj.get(cur) || [];
for (const nxt of neighbors) {
if (!dist.has(nxt)) {
dist.set(nxt, dist.get(cur) + 1);
queue.push(nxt);
}
}
}
return -1;
}동작 순서를 정리하면 이렇다.
- 단위 칸 채우기: 좌표 0~49 범위의 모든 1×1 칸에 대해, 어떤 직사각형이든 그 칸을 완전히 덮고 있으면
true로 표시한다. - 경계 변 찾기: 모든 격자점에서 뻗어나가는 가로/세로 변을 순회하면서, 그 변을 사이에 둔 두 칸의 내부 여부가 다를 때만(
!==) 그 변을 그래프의 간선으로 추가한다. - BFS: 이렇게 만든 "둘레 전용 그래프" 위에서 캐릭터 위치부터 아이템 위치까지 최단 거리를 구한다.
이 방식은 애초에 "칸이 이어져 있는지"를 묻지 않기 때문에, 오목한 지형이든 가운데 구멍이 뚫린 도넛 모양이든 상관없이 안전하게 동작한다.
다만 코드만 보면 각 부분이 정확히 뭘 하는 건지 한눈에 안 들어올 수 있어서, 작은 예시를 하나 잡고 실제로 손으로 따라가 보겠다.
cellFilled가 표현하는 것
cellFilled[x][y]는 좌표 (x, y)를 왼쪽 아래 꼭짓점으로 하는 가로세로 1짜리 정사각형이 도형 내부에 속하는지를 저장한다.
즉 이 배열의 인덱스는 "점"이 아니라 "칸"을 가리킨다.
for (let x = x1; x < x2; x++) {
for (let y = y1; y < y2; y++) {
cellFilled[x][y] = true;
}
}여기서 x < x2처럼 오른쪽 끝을 포함하지 않는 것이 중요하다.
직사각형이 [x1, y1, x2, y2]로 주어지면, 그 직사각형이 덮는 단위 칸은 딱 x1부터 x2-1까지, y1부터 y2-1까지다.
예를 들어 [1, 1, 3, 2](가로 2, 세로 1짜리 직사각형)라면 x는 1과 2, y는 1만 해당하니 cellFilled[1][1]과 cellFilled[2][1] 두 칸만 true가 된다.
가로변/세로변 판정이 뜻하는 것
헷갈리기 쉬운 부분이 "위쪽 셀"과 "아래쪽 셀"을 가리키는 인덱스다.
격자점 (x, y)에서 오른쪽으로 뻗는 가로변 (x, y)–(x+1, y)를 기준으로 그리면 이렇다.
y+1 ┌────────┐
│ 위쪽 셀 │ cellFilled[x][y] (y ~ y+1 구간)
y ├────────┤ ← 지금 보는 가로변 (x,y)-(x+1,y)
│ 아래쪽 셀│ cellFilled[x][y-1] (y-1 ~ y 구간)
y-1 └────────┘
x x+1cellFilled[x][y]는 정의상 "y부터 y+1까지" 구간을 칠하므로 이 변 기준으로는 위쪽 칸이고, cellFilled[x][y-1]은 "y-1부터 y까지"를 칠하므로 아래쪽 칸이다.
두 칸 중 하나만 도형 내부라면(above !== below) 그 사이에 낀 가로변은 안쪽과 바깥쪽을 가르는 경계선이라는 뜻이므로 캐릭터가 밟을 수 있는 변이 된다.
세로변도 완전히 같은 논리로, 오른쪽 칸 cellFilled[x][y]와 왼쪽 칸 cellFilled[x-1][y]를 비교한다.
배열 범위를 벗어난 칸은 filled() 함수가 false를 돌려주게 해뒀는데, 이게 은근히 중요하다.
덕분에 도형의 가장 바깥쪽 테두리도 "칠해진 칸과, 범위 밖이라 항상 빈 칸인 가짜 칸"의 경계로 자동으로 잡힌다.
따로 "이건 맨 바깥 테두리니까 예외처리"를 할 필요가 없다.
작은 예시로 직접 따라가보기
직사각형 하나, [1, 1, 3, 2](가로 2, 세로 1)로 손으로 그래프를 만들어보면 이렇다.
앞서 계산한 대로 cellFilled[1][1]과 cellFilled[2][1]만 true다.
모든 격자점 쌍에 대해 가로변/세로변 조건을 체크해보면, 실제로 경계로 잡히는 변은 이 6개뿐이다.
(1,2) ●───● (2,2) ───● (3,2)
│ │
│ 내부 칸 2개 │
│ │
(1,1) ●───● (2,1) ───● (3,1)정확히 직사각형의 둘레 6칸(가로 2 + 세로 1을 두 번 더한 값)만 간선으로 잡히고, 칸 내부를 가로지르는 (2,1)-(2,2) 같은 변은 양쪽 다 내부 칸이라 제외된다는 걸 확인할 수 있다.
이 그래프에서 캐릭터가 (1,1), 아이템이 (3,2)에 있다고 하면, BFS는 (1,1) → (2,1) → (3,1) → (3,2) 또는 (1,1) → (1,2) → (2,2) → (3,2) 두 경로를 발견하고 둘 다 길이 3이므로 3을 반환한다.
실제로 마주보는 두 꼭짓점 사이의 최단 둘레 거리는 전체 둘레(6)의 절반이니 손으로 계산한 값과도 일치한다.
BFS 파트
인접 리스트는 좌표 (x, y)를 key(x, y) = x * 60 + y라는 하나의 숫자로 압축해서 Map의 키로 쓴다.
좌표 범위가 0~50이라 60을 곱해도 서로 다른 좌표가 같은 키로 겹칠 일이 없다.
dist 맵은 "이미 방문했는가"와 "출발점부터의 거리가 몇인가"를 동시에 담당해서, 방문 체크용 배열을 따로 두지 않고도 dist.has(nxt)로 방문 여부를, dist.get(cur)로 현재까지의 거리를 관리한다.
나머지는 표준적인 큐 기반 BFS로, 아이템 위치의 키를 큐에서 꺼내는 순간 그때까지 쌓인 거리가 바로 정답이다.
검증
프로그래머스에서 제공하는 입출력 예제 5개를 전부 돌려봤다.
| 케이스 | 기대값 | 결과 |
|---|---|---|
| 예제 1 (사각형 4개) | 17 | 17 ✅ |
| 예제 2 (사각형 4개) | 11 | 11 ✅ |
| 예제 3 (사각형 1개) | 9 | 9 ✅ |
| 예제 4 (사각형 2개) | 15 | 15 ✅ |
| 예제 5 (사각형 3개) | 10 | 10 ✅ |
모두 통과했다.
정리
이 문제를 풀면서 배운 건 사실 알고리즘 자체보다 이거였다.
- "다들 이렇게 푼다더라" 하는 풀이를 볼 때, 왜 그렇게 하는지 원리를 이해하지 않고 형태만 따라 하면 디테일 하나를 놓치는 순간 전혀 동작하지 않는 코드가 나온다. 처음에 짠 "2배 확대" 코드가 딱 그 꼴이었다.
- 픽셀(칸) 기반으로 도형의 경계를 다루는 문제는 4-연결/8-연결 문제를 항상 의심해봐야 한다. 특히 오목한 도형이나 도넛 모양처럼 안쪽에 구멍이 있는 형태에서는 거의 반드시 걸린다.
- 막힐 때는 실제로 격자를 그려서 눈으로 확인하고, 연결 요소 개수를 코드로 세어보는 게 "왜 안 되는지"를 파악하는 데 훨씬 빠르다. 감으로 좌표를 이리저리 바꿔보는 것보다 훨씬 확실했다.
같은 함정에 빠진 사람이 있다면 도움이 되길 바란다.
'알고리즘 문제풀이 > 프로그래머스 Level 3' 카테고리의 다른 글
| [JavaScript] 네트워크 (0) | 2026.08.15 |
|---|
