추천) 1210. ladder1 문제를 먼저 풀기를 추천한다.
https://masso.tistory.com/23?category=881145
[D4] 1210.Ladder1
입력) 총 10개의 테스트 케이스 테스트 케이스의 번호, 사다리 정보가 들어있는 100 x 100 크기의 이차원 배열 (0: 아무것도 없음, 1 : 사다리, 2 : 도착 지점) 출력) # 해당 테스트 케이스 번호, 지정된
masso.tistory.com
입력)
총 10개의 테스트 케이스
테스트 케이스의 번호, 사다리 정보가 들어있는 100 x 100 크기의 이차원 배열
(0: 아무것도 없음, 1 : 사다리, 2 : 도착 지점)
출력)
# 해당 테스트 케이스 번호, 가장 짧은 이동 거리를 가지는 사다리의 y index 출력
입, 출력 분석)
입력을 보면 마지막 줄에 존재해야할 2가 없음에 주의해야 한다.
핵심)
1210. ladder1 문제 풀이 링크 참고
입력 분석을 통해
- x == 99에 도달할 때까지, 가장 짧은 칸을 이동해온 y index를 구해야 함을 알았다.
복수 개인 경우 가장 큰 x좌표
- y(0 -> 99)로 탐색하며, 짧거나 같은 거리를 가지는 사다리가 있을 때 y index를 갱신하면 된다.
예시 분석)
(생략)
실수)
- 도착 지점에 도착하는 사다리 중에 짧은 거리를 가지는 사다리를 구하는 문제인 줄 알았는데,가만히 입력을 보니까 2가 없는 것을 알게 되었다. (이래서 사람이 편견이 무섭다)
구현)
#include<iostream>
using namespace std;
int map[100][100]; // 100x100 크기의 이차원 배열
int dx[3] = { 1, 0, 0 }; // 0: 아래, 1: 왼쪽, 2: 오른쪽
int dy[3] = { 0, -1, 1 }; // 0: 아래, 1: 왼쪽, 2: 오른쪽
int main(int argc, char** argv) {
int test_case, T = 0, ans = 0;
for (test_case = 1; test_case <= 10; ++test_case) {
scanf("%d", &T);
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++)
scanf("%d", &map[i][j]);
}
int minLen = 10000; // 0. minLen 정의
for (int j = 0; j < 100; j++) {
if (!map[0][j]) continue;
int x = 0, y = j, dir = 0, len = 1; // 1. len 정의
while (x < 100) {
int cnt = 0, key = 0;
for (int i = 0; i < 3; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= 100 || ny < 0 || ny >= 100) continue;
if (map[nx][ny]) {
cnt++; key += i; // 아래 0, 왼 1, 오 2
}
}
if (cnt == 2 && key < 3) { // 회전
if (dir == 0) dir = key;
else dir = 0;
}
if (x == 99) break;
x += dx[dir]; y += dy[dir]; len++; // 2. 총 len 구하기
}
if(minLen >= len){ // 3. len 갱신하기
minLen = len;
ans = j;
}
}
printf("#%d %d \n", T, ans);
}
return 0;
}'Algorithm&Problem > [Problems] SWEA' 카테고리의 다른 글
| BOJ[20055]. 컨베이어 벨트 위의 로봇 (0) | 2021.04.21 |
|---|---|
| [D3] 1209. Sum (0) | 2020.08.22 |
| [D4] 1210.Ladder1 (0) | 2020.08.18 |
| [D3] 1206. View (0) | 2020.08.08 |
| [D3] 1208. Flatten (0) | 2020.07.25 |
