반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 소프티어
- 성적평가
- 6987
- upper_bound
- 기술면접
- 퇴사통보
- compose
- boj #19237 #어른 상어
- 오퍼레터
- msSQL
- 처우산정
- OFFSET
- 처우협의
- Docker
- @P0
- 백준
- 경력
- incr
- 13908
- BFS
- 백트래킹
- 이분탐색
- dfs
- 파라메트릭
- BOJ
- 연결요소
- 물채우기
- softeer
- 매개변수탐색
- Kafka
Archives
- Today
- Total
기술 블로그
길 확인하기 본문
728x90
반응형
문제 저작권상 간략하게 올린다.
(0, 0)에서 출발하여 (7, 7)로 도달할 수 있는가?
단, 0은 벽, 1은 좌우 이동 가능, 2는 상하 이동 가능, 3은 상우 이동 가능, 4는 좌하 이동 가능이다.
※ 알게된 것
2차원 격자에서 두 방향으로만 이동 가능한 이런 문제는 DFS/BFS를 굳이 안 써도,
대부분 반복문만으로 해결 가능하다. (물론 우회나 퇴보는 불가능)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | #include <iostream> #include <queue> #include <cstdio> #include <vector> #include <cstring> #include <string> #include <math.h> #include <algorithm> using namespace std; int main(void) { int T = 0; int map[8][8] = { 0, }; bool Check[8][8] = { false, }; scanf("%d", &T); for (int tc = 1; tc <= T; tc++) { memset(map, 0, sizeof(map)); memset(Check, false, sizeof(Check)); for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { scanf("%d", &map[i][j]); } } Check[0][0] = true; // 출발점은 true // 오른쪽과 아래로만 이동하므로, 단순 2중 for문 가능 for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { // 이번 칸이 도착지까지 도달 할 수 없는 칸이라면 고려할 필요 없다. if (!Check[i][j]) continue; if (map[i][j] == 1 || map[i][j] == 3) // 현재 있는 곳이 오른쪽으로 갈 수 있는 곳이라면 { if (j + 1 < 8 && (map[i][j + 1] == 1 || map[i][j + 1] == 4)) { // (다음 칸 기준) 다음 칸이 왼쪽에서 들어올 수 있는 칸이라면 Check[i][j + 1] = true; } } else if (map[i][j] == 2 || map[i][j] == 4) // 현재 있는 곳이 아래로 내려갈 수 있는 곳이라면 { if (i + 1 < 8 && (map[i + 1][j] == 2 || map[i + 1][j] == 3)) { // 아래에 있는 칸 기준으로 아래 칸이 위쪽에서 들어올 수 있는 칸이라면 Check[i + 1][j] = true; } } } } if (Check[7][7]) printf("YES\n"); else printf("NO\n"); } return 0; } | cs |
728x90
반응형
'알고리즘 문제 > 기타' 카테고리의 다른 글
Zero One Algorithm Contest 2018 (0) | 2019.01.03 |
---|---|
막대 그래프 그리기 (0) | 2018.10.27 |
길이가 N인 이진수 (0) | 2018.10.26 |
배열 속 원소들 확인하기 (0) | 2018.10.05 |
[카카오 코드 페스티벌 2018 예선 A] 상금헌터 (0) | 2018.09.18 |