문제
https://school.programmers.co.kr/learn/courses/30/lessons/169199?language=cpp
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입출력

해설
격자무늬가 주어졌을 때 목표지점까지 도달하는 최소 이동횟수를 구하는 문제이다.
이동하는 방식은 한 번 움직이면 미끄러지는 방식으로 '벽' 또는 '장애물'을 부딪혔을 때까지 움직일 수 있다.
그러면 한 번 움직일 때 계속하여 한 방향으로 움직일 수 있도록 해주어야 한다.
또한 한 번 도달한 곳에서는 다시 방문할 이유가 없기 때문에 방문배열을 2차원으로 선언하면 된다.
결론적으로 다음과 같은 로직으로 풀이가 진행된다.
1. 초기위치와 종료위치를 찾는다.
2. 초기위치부터 시작하여 BFS를 돌린다.
3. BFS 돌릴 때 한 지점으로부터 다른 방향으로는 계속하여 움직일 수 있게 한다.
4. 종료위치가 나올 시에 종료하여 결과를 리턴한다.
정답코드
더보기
#include <bits/stdc++.h>
using namespace std;
/*
격자무늬에서 목표지점까지 도달하여라
1. 한 번 움직일 때 벽 or 장애물까지만 도달할 수 있음.
2. 방문배열을 한 번 씩만 도달할 수 있음.
1. 초기 위치를 찾는다.
2. 목표 위치를 찾는다.
3. bfs를 돌린다.
4. 결론 위치를 리턴한다.
*/
pair<int, int> findLocation(char target, vector<string>& board){
pair<int, int> loc{-1, -1};
for(int i{}; i < board.size(); i++){
for(int j{}; j < board[i].size(); j++){
if (board[i][j] == target){
loc = {i, j};
}
}
}
return loc;
}
bool isBoundary(int x, int y, vector<string>& board){
return x >= 0 && x < board.size() && y >=0 && y < board[0].size();
}
int visited[102][102];
int solution(vector<string> board) {
int answer = 0;
auto [sx, sy] = findLocation('R', board);
auto [ex, ey] = findLocation('G', board);
// cout << sx << ' ' << sy << ' ' << ex << ' ' << ey << '\n';
queue<pair<int, int>>q;
q.push({sx, sy});//초기 위치 보내기
memset(visited, -1, sizeof visited);
visited[sx][sy] = 0;
int dx[]{0, 1, 0, -1};//동남서북
int dy[]{1, 0, -1, 0};
//반대면 0, 2
//i + 2 1, 3
//int repeat{};
while(!q.empty()){
auto[x, y] = q.front();q.pop();
//repeat++;
if(x == ex && y == ey){break;}
//방향 정하기
for(int i{};i < 4; i++){
//벽을 만나거나, 장애물을 만나기 전까지 이동하기
int nx = x;
int ny = y;
//cout << "위치" << nx << ' ' << ny << '\n';
while(isBoundary(nx, ny, board) && board[nx][ny] != 'D'){//벽 장애물
nx = nx + dx[i];
ny = ny + dy[i];
//cout << "바뀐 위치" << nx << ' ' << ny << '\n';
}
//벽이라면 그 직전까지는 이동해야 됨.
if(!isBoundary(nx, ny, board) || board[nx][ny] == 'D'){
//반대로 이동을 한 번 해보자.
nx = nx + dx[(i + 2)%4];
ny = ny + dy[(i + 2)%4];
//cout << "재조정" << nx << ' ' << ny << '\n';
}
if(visited[nx][ny] != -1)continue;
visited[nx][ny] = visited[x][y] + 1;
q.push({nx, ny});
}
}
// for(int i{}; i < board.size(); i++){
// for(int j{}; j < board[0].size(); j++){
// cout << visited[i][j] << ' ';
// }
// cout << '\n';
// }
return visited[ex][ey];
}
깃허브 : https://buly.kr/Chq8WP9
'코딩테스트 > programmers' 카테고리의 다른 글
| 프로그래머스 / 구현 / 행렬 테두리 회전하기 (0) | 2026.01.17 |
|---|---|
| 프로그래머스 / DFS / 무인도 여행 (0) | 2026.01.16 |
| 프로그래머스 / 정수론 / 124 나라의 숫자 (0) | 2025.12.27 |
| 프로그래머스 / 정수론 / 소수 찾기 (0) | 2025.12.22 |
| 프로그래머스 / 다익스트라 / 배달 (0) | 2025.12.22 |