[Codeground 12번] 방속의 거울

문제 출처 :

https://www.codeground.org/practice/practiceProblemList

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

구현문제이다.

빛이 어느방향에서 왔을 때 그때 거울 모양이 / 모양인지 /가 뒤집힌 모양인지에 따라 방향을 결정해주면 된다.

n이 1000이라 시간 복잡도가 O(n^2)에 충분히 끝날 수 있다.

그리고 거울의 이용여부는 visit배열을 이용하여 해결하면 된다.

소스 코드 : 

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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

#include <iostream> #include <cstdio> #include <memory.h>   #define LEFT 1 #define RIGHT 2 #define UP 3 #define DOWN 4   using namespace std;   int map[1001][1001]; bool visit[1001][1001];   int n; bool chkRange(int y, int x) {     if (!(0 <= y && y < n) || !(0 <= x && x < n))         return false;       return true; }   int main() {     int tCase;     scanf("%d", &tCase);       for (int tc = 1; tc <= tCase; tc++)     {         scanf("%d", &n);         memset(visit, false, sizeof(visit));           for (int i = 0; i < n; i++)             for(int j = 0 ; j < n; j++)                 scanf("%1d", &map[i][j]);           int x, y, dir = RIGHT;         x = y = 0;           int cnt = 0;           while (chkRange(y, x))         {             if (map[y][x] && !visit[y][x])             {                 visit[y][x] = true;                 cnt++;             }             if (map[y][x] == 2)             {                 if (dir == UP)                     dir = LEFT;                 else if (dir == DOWN)                     dir = RIGHT;                 else if (dir == LEFT)                     dir = UP;                 else if (dir == RIGHT)                     dir = DOWN;             }               else if (map[y][x] == 1)             {                 if (dir == UP)                     dir = RIGHT;                 else if (dir == DOWN)                     dir = LEFT;                 else if (dir == LEFT)                     dir = DOWN;                 else if (dir == RIGHT)                     dir = UP;             }               if (dir == UP)                 y--;             else if (dir == DOWN)                 y++;             else if (dir == LEFT)                 x--;             else if (dir == RIGHT)                 x++;         }           printf("Case #%d\n%d\n", tc, cnt);     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus