OJ 1726 : 로봇 - C++
로봇
코드
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ll long long
using namespace std;
// 1132 ~ 0140
struct Pos{
int r;
int c;
int dir;
};
int dr[4] = {1, 0, -1, 0};// 남 서 북 동
int dc[4] = {0, -1, 0, 1};
int M,N,ans=1e9;
int board[105][105]; // 1~100 인덱스 사용
int cost[4][105][105];
Pos start;
Pos dest;
/* 문제의 방향을 right/left 하기 좋은 내 방향으로 바꾸기 */
int changeDir(int d)
{
if(d == 1) return 3;
if(d == 2) return 1;
if(d == 3) return 0;
return 2;
}
/* cur에서 right/left로 얼마나 했을 때 hope로 갈수 있는지 최소값 */
int diffDir(int cur, int hope)
{
if(cur == hope) return 0;
int cur_t = cur;
int leftCnt=0;
while(cur_t != hope){
cur_t--;
if(cur_t<0) cur_t +=4;
leftCnt++;
}
cur_t = cur;
int rightCnt=0;
while(cur_t != hope){
cur_t++;
if(cur_t>3) cur_t -=4;
rightCnt++;
}
return min(leftCnt, rightCnt); // 왼쪽, 오른쪽 회전 중 최소 값 리턴
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> M >> N; // M=세로, N=가로
for(int i=1;i<=M;i++)
for(int j=1;j<=N;j++)
cin >> board[i][j];
cin >> start.r >> start.c >> start.dir;
cin >> dest.r >> dest.c >> dest.dir;
start.dir = changeDir(start.dir);
dest.dir = changeDir(dest.dir);
/* 에외처리 - 출발점과 도착점이 같다면 방향 회전으로만 답을 구할 수 있음 */
if(dest.r == start.r and dest.c == start.c){
cout << diffDir(dest.dir, start.dir);
return 0;
}
/* cost초기화 */
for(int z=0;z<4;z++)
for(int i=1;i<=M;i++)
fill(cost[z][i], cost[z][i]+N+1, 1e9);
queue<Pos> q;
q.push(start);
cost[start.dir][start.r][start.c] = 0;
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int d=0;d<4;d++)
{
int nr = cur.r;
int nc = cur.c;
for(int n=1;n<=3;n++)
{
nr += dr[d];
nc += dc[d];
int dval = diffDir(cur.dir, d); // 오른쪽, 왼쪽 회전중 최소 회수
int destval = 0;
// 목적지라면 최종 방향도 cost계산을 해줘야함
if(nr == dest.r and nc == dest.c) destval = diffDir(d, dest.dir);
if(nr<1 or nc<1 or nr>M or nc>N) break; // 범위를 벗어나면 종료
if(board[nr][nc] == 1) break; // 벽을 만나도 종료
/* cost의 길이가 같은 경우에 continue 해주지 않으면 무한루프에 걸림
--> 값이 동일하면 어차피 그 좌표에서 그 방향을 가졌으면 같은 결과를 산출 */
if(cost[d][nr][nc] <= cost[cur.dir][cur.r][cur.c] + dval + destval + 1) continue;
cost[d][nr][nc] = cost[cur.dir][cur.r][cur.c] + dval + destval + 1;
if(nr == dest.r and nc == dest.c) continue;
Pos t = {nr, nc, d};
q.push(t);
}
}
}
for(int d=0;d<4;d++)
ans=min(cost[d][dest.r][dest.c], ans);
cout << ans;
return 0;
}
- 핵심
board[dir][r][c]
를 사용해서 보드판의 입장
에서 어떤 방향을 가지고 있는지
에 따라 최소 값 갱신
cost를 비교
할 때 같은 cost
를 가지면 반드시 continue
로 넘겨줘야 한다
--> 그렇지 않으면 무조건 무한루프에 빠진다
출발지점
과 도착지점
이 같은 경우
예외처리
right / left 회전
중 최소 회전
을 찾는 diffDir
정의
- 느낀 점
프로그래머스
의 활주로 건설
이라는 문제로 처음 board 상태에 따른 3차원 배열
을 접했는데 종종 나오는 것 같다
Author And Source
이 문제에 관하여(OJ 1726 : 로봇 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-1726-로봇-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #include <deque> #include <numeric> #include <map> #include <stack> #define ll long long using namespace std; // 1132 ~ 0140 struct Pos{ int r; int c; int dir; }; int dr[4] = {1, 0, -1, 0};// 남 서 북 동 int dc[4] = {0, -1, 0, 1}; int M,N,ans=1e9; int board[105][105]; // 1~100 인덱스 사용 int cost[4][105][105]; Pos start; Pos dest; /* 문제의 방향을 right/left 하기 좋은 내 방향으로 바꾸기 */ int changeDir(int d) { if(d == 1) return 3; if(d == 2) return 1; if(d == 3) return 0; return 2; } /* cur에서 right/left로 얼마나 했을 때 hope로 갈수 있는지 최소값 */ int diffDir(int cur, int hope) { if(cur == hope) return 0; int cur_t = cur; int leftCnt=0; while(cur_t != hope){ cur_t--; if(cur_t<0) cur_t +=4; leftCnt++; } cur_t = cur; int rightCnt=0; while(cur_t != hope){ cur_t++; if(cur_t>3) cur_t -=4; rightCnt++; } return min(leftCnt, rightCnt); // 왼쪽, 오른쪽 회전 중 최소 값 리턴 } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> M >> N; // M=세로, N=가로 for(int i=1;i<=M;i++) for(int j=1;j<=N;j++) cin >> board[i][j]; cin >> start.r >> start.c >> start.dir; cin >> dest.r >> dest.c >> dest.dir; start.dir = changeDir(start.dir); dest.dir = changeDir(dest.dir); /* 에외처리 - 출발점과 도착점이 같다면 방향 회전으로만 답을 구할 수 있음 */ if(dest.r == start.r and dest.c == start.c){ cout << diffDir(dest.dir, start.dir); return 0; } /* cost초기화 */ for(int z=0;z<4;z++) for(int i=1;i<=M;i++) fill(cost[z][i], cost[z][i]+N+1, 1e9); queue<Pos> q; q.push(start); cost[start.dir][start.r][start.c] = 0; while(!q.empty()) { auto cur = q.front(); q.pop(); for(int d=0;d<4;d++) { int nr = cur.r; int nc = cur.c; for(int n=1;n<=3;n++) { nr += dr[d]; nc += dc[d]; int dval = diffDir(cur.dir, d); // 오른쪽, 왼쪽 회전중 최소 회수 int destval = 0; // 목적지라면 최종 방향도 cost계산을 해줘야함 if(nr == dest.r and nc == dest.c) destval = diffDir(d, dest.dir); if(nr<1 or nc<1 or nr>M or nc>N) break; // 범위를 벗어나면 종료 if(board[nr][nc] == 1) break; // 벽을 만나도 종료 /* cost의 길이가 같은 경우에 continue 해주지 않으면 무한루프에 걸림 --> 값이 동일하면 어차피 그 좌표에서 그 방향을 가졌으면 같은 결과를 산출 */ if(cost[d][nr][nc] <= cost[cur.dir][cur.r][cur.c] + dval + destval + 1) continue; cost[d][nr][nc] = cost[cur.dir][cur.r][cur.c] + dval + destval + 1; if(nr == dest.r and nc == dest.c) continue; Pos t = {nr, nc, d}; q.push(t); } } } for(int d=0;d<4;d++) ans=min(cost[d][dest.r][dest.c], ans); cout << ans; return 0; }
- 핵심
board[dir][r][c]
를 사용해서보드판의 입장
에서어떤 방향을 가지고 있는지
에 따라최소 값 갱신
cost를 비교
할 때같은 cost
를 가지면반드시 continue
로넘겨줘야 한다
--> 그렇지 않으면 무조건무한루프에 빠진다
출발지점
과도착지점
이같은 경우
예외처리
right / left 회전
중최소 회전
을 찾는diffDir
정의
- 느낀 점
프로그래머스
의활주로 건설
이라는 문제로 처음board 상태에 따른 3차원 배열
을 접했는데종종 나오는 것 같다
Author And Source
이 문제에 관하여(OJ 1726 : 로봇 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-1726-로봇-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)