문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/81302?language=cpp
카카오 기출문제 중 Level 2 난이도, 그림만 많지 문제를 이해하기에는 어렵지 않다.
X는 칸막이로 치고, 그냥 5x5 맵에 P와 P 사이에 맨해튼 거리를 계산하면 된다.
문제 핵심 및 풀이
키포인트는 5 x 5 맵이 5개 있다는 점.
탐색 범위가 작아 완전 탐색이든 뭐든 시간적인 제약은 없다.
또한 핵심 아이디어는 이 문제가 그래프 탐색을 할 수 있다는 것.
그중에서 편한 방법은 BFS인데, 왜냐하면 BFS를 통해 최단거리를 쉽게 구할 수 있기 때문이다.
이 문제를 왜 BFS로 풀 수 있을까?
맨해튼 거리를 계산하는 것이기 때문이다.
두 점 A와 B의 좌표를 (x, y)라고 했을 때
맨해튼 거리는 | a.x - b.x | + | a.y - b.y |
이는 한 점에서 한 점으로 가는 최단 거리를 계산한 것이다.
그렇기 때문에 아래와 같이 생각할 수 있다.
위 예시에서 맨해튼 거리는? 1이다.
즉, 위는 거리 두기가 지켜지지 않은 예시이다.
여기서 중간에 칸막이가 있는 상태로 생각해 보자.
여기서는 칸막이로 막혀있기 때문에 거리 두기가 지켜졌다.
또한 문제 예시로 나온 것을 살펴보면
5x5 중 2x2 만 그렸다.
여기서 X를 벽이라고 생각하고, P에서 P로 가는 최단거리를 구한다고 가정해 보자.
첫 번째 것을 제외하고선 모두 2번 이하로 가능하다.
그래서 이 문제는
한 점 P에서 출발하여 다른 P로 가는 최단거리 중에 2 이하가 하나라도 존재하면 실패
이런 식으로 치환할 수 있다.
즉 BFS를 통해 거리가 2 이하인지만 확인해 주면 된다.
실수하기 쉬운 부분
입력으로 5개의 다른 맵이 들어오기 때문에 맵을 5번 갱신하고, BFS를 5번 해줘야 한다.
그래서 만약 BFS에서 전역 변수를 사용할 경우, 전역 변수를 초기화해 주는 작업이 필요하다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
char map[5][5];
// 상하좌우
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
// 한 점 p와 p에서 2이하인게 하나라도 존재하면 false 반환
bool bfs(int sx, int sy){
queue<pair<int,int>> q;
// 5x5 방문배열 0으로 초기화
int visited[5][5];
fill(&visited[0][0],&visited[4][5],0);
// 0이 미방문 처리기 때문에 1로 만들어주고, 마지막에 1을 빼주는 것으로 한다.
visited[sx][sy] = 1;
q.push({sx,sy});
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >=5 || ny >= 5 ||
visited[nx][ny] != 0 || map[nx][ny] == 'X') continue;
visited[nx][ny] = visited[x][y]+1; // 현재까지 움직인 거리 + 1
// P를 만날경우 해당 거리가 2 (여기서는 1부터 시작했기 때문에 3) 이하인지 확인한다.
if(map[nx][ny] == 'P' && visited[nx][ny] <= 3) return false;
// O를 만날 경우 탐색을 계속하기 위해 큐에 넣음
if(map[nx][ny] == 'O') q.push({nx,ny});
}
}
return true; // 모든 케이스를 통과하면 true
}
vector<int> solution(vector<vector<string>> places) {
vector<int> answer(5,1); // {1,1,1,1,1} 로 초기화
// 모든 맵을 하나씩 돌림
for(int i = 0; i < places.size(); i++){
vector<pair<int,int>> seat; // p의 위치를 저장
// 맵을 구성해준다.
for(int j = 0; j < places[i].size(); j++){
for(int k = 0; k < places[i][j].size(); k++){
map[j][k] = places[i][j][k];
// P일 경우 seat 리스트에 담아줌
if(map[j][k] == 'P') seat.push_back({j,k});
}
}
// 모든 p에서 BFS를 돌려줘서 p간의 거리 확인
for(int j = 0; j < seat.size(); j++){
if(!bfs(seat[j].first,seat[j].second)){
answer[i] = 0; // 실패하면 0
break;
}
}
// 성공하면 기존이 상태 1이 유지
}
return answer;
}↑
Java 구현 코드
↓
import java.util.*;
import java.lang.*;
class Solution{
// 상하좌우
static int[] dx = {0,0,-1,1};
static int[] dy = {-1,1,0,0};
static char[][] map = new char[5][5]; // 맵
// 좌표를 나타내기 위해 Point라는 클래스 생성
class Point{
int x,y;
// 생성자
Point(int x, int y){
this.x = x;
this.y = y;
}
}
// bfs를 통해 매개변수 좌표에서 다른 p와의 거리를 모두 계산
int bfs(Point sp){
Queue<Point> q = new LinkedList<Point>();
int[][] visited = new int[5][5]; // 방문 배열 추가
for(int i = 0; i <= 4; i++) Arrays.fill(visited[i],0); // 모두 0으로 초기화
visited[sp.x][sp.y] = 1; // 0이 미방문이기 때문에 1로 올리고 최종결과에서 빼줌
q.add(new Point(sp.x,sp.y));
while(q.size() > 0){
Point p = q.poll();
Point t = new Point(p.x,p.y);
int x = t.x;
int y = t.y;
for(int i = 0; i < 4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5 ||
visited[nx][ny] != 0 || map[nx][ny] == 'X') continue;
visited[nx][ny] = visited[x][y]+1; // 해당 좌표까지 움직인 거리 + 1
// P를 만나고, 이동거리가 2(여기서는 1로 시작했기 때문에 3)일 경우 실패
if(map[nx][ny] == 'P' && visited[nx][ny] <= 3){
return 0;
}
// O를 만날 경우 탐색 진행을 위해 해당 좌표를 큐에 넣음
if(map[nx][ny] == 'O') {
Point np = new Point(nx,ny);
q.add(np);
}
}
}
return 1; // 모든 케이스를 통과하면 성공
}
public int[] solution(String[][] places) {
int[] answer = {1,1,1,1,1};
int idx = 0;
// 모든 맵에 대해서 돌려줌
for(String[] place : places){
List<Point> seat = new ArrayList<Point>(); // P들이 있는 좌표를 저장
for(int i = 0; i < place.length; i++){
char[] arr = place[i].toCharArray();
for(int j = 0; j < arr.length; j++){
map[i][j] = arr[j];
if(map[i][j] == 'P') seat.add(new Point(i,j));
}
}
// 해당 맵의 모든 p 위치에서 BFS를 돌려 p 간의 거리 확인
for(int i = 0; i < seat.size(); i++){
int x = seat.get(i).x;
int y = seat.get(i).y;
int num = bfs(new Point(x,y));
// 0이 나오면 실패한 것
if(num == 0){
answer[idx] = 0;
break;
}
}
idx++; // answer에 관련된 인덱스
}
return answer;
}
}↑
시행착오
문제가 어렵진 않았다. 쉽게 접근하고 구현하였는데
코드 실수 때문에 엄청 오래 디버깅했다..
while문을 if문으로 써놓고 이걸 모르고 있었다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me