백준 16197 두 동전

문제 URL : https://www.acmicpc.net/problem/16197

16197번: 두 동전

 

문제 접근법 : 

bfs로 두동전을 좌우상하 같은 방향으로 동시에 움직이지만 하나가 벽때문에 움직일수 없어도 다른하나는 움직일수있다면 하나라도 움직이게 해줘야 합니다. 

 

1. map의 사이즈를 [n+2][n+2] 까지 잡아 움직이는 행열의 범위를  0~n+1 까지 움직일수 있게해줍니다 다만 행열의 위치가 0 이나 n+1 일때는 밖으로 나가는 것을 표현해주고 그외는 맵의 범위대로 움직이는것을 표현합니다. 

2. 하나만 떨어지고 하나는 떨어지면 안된다는것을 반드시 인지하시고

3.이동횟수가 10번이 넘지 않는다는 조건또한 잊으시면 안됩니다. (문제 제대로 안읽고 이동횟수 제한때문에 여러번 틀렸네요..)

4. 그리고 마지막으로 두동전이 같이 움직이기위해 visit 처리는 4차원 배열을 이용합니다

 

소스코드:

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 <vector> #include <queue> #include <algorithm> using namespace std; int n, m; int dy[4] = { -1, 0, 1, 0 }; int dx[4] = { 0, 1, 0, -1 }; char visit[21][21][21][21];//왼쪽 2개는 1번코인, 나머지는 2번코인 움직이는  char map[22][22]; vector<pair<int, int>> cv;//코인의 위치 담는 벡터 struct coin{     int y1, x1, y2, x2, cnt;     coin(int y1, int x1, int y2, int x2, int cnt)         :y1(y1), x1(x1), y2(y2), x2(x2), cnt(cnt){} }; bool isrange(int y, int x){//맵의 범위     if (1 <= y&&y <= n && 1 <= x&&x <= m)         return true;     return false; }   int bfs() {     queue<coin> q;     int y1 = cv[0].first;     int x1 = cv[0].second;     int y2 = cv[1].first;     int x2 = cv[1].second;     q.push({ y1, x1, y2, x2, 0 });//코인 1,2의 위치와 이동횟수를 q에 넣음     while (!q.empty())     {         y1 = q.front().y1;         x1 = q.front().x1;         y2 = q.front().y2;         x2 = q.front().x2;         int cnt = q.front().cnt;         q.pop();                  bool isfall1 = false;//1번 코인이 바닥에 떨어졌는지         bool isfall2 = false;//마찬가지로 2번 코인                  if (cnt > 10)//이동횟수가 10번넘는다면 -1출력             return -1;         if (!isrange(y1, x1))//범위 밖인지             isfall1 = true;         if (!isrange(y2, x2))             isfall2 = true;         if (isfall1 ^ isfall2)//둘중 한개만 떨어진경우 한개만 떨어저야 하므로 xor 연산을 해주면됩니다             return cnt;           if (!isfall1&&!isfall2)//둘다 false라는 뜻은 둘다 맵범위 안에있다는 뜻         {             if (visit[y1][x1][y2][x2])//방문했는지                 continue;//방문했었더라면 다음껄 바로 봐야함             visit[y1][x1][y2][x2] = 1; //방문처리             for (int i = 0; i < 4; i++)             {                 int ny1 = y1 + dy[i];                 int nx1 = x1 + dx[i];                 int ny2 = y2 + dy[i];                 int nx2 = x2 + dx[i];                 if (map[ny1][nx1] == '#')//다음 움직일것이 벽이라면 움직이지 말아야함                     ny1 = y1, nx1 = x1;                 if (map[ny2][nx2] == '#')                     ny2 = y2, nx2 = x2;                 q.push({ ny1, nx1, ny2, nx2, cnt + 1 });             }         }     }     return -1; } int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     cin >> n >> m;     for (int i = 1; i <= n; i++)     {         for (int j = 1; j <= m; j++){             cin >> map[i][j];             if (map[i][j] == 'o'){//코인의 위치를 저장하고 그자리를 .으로 변경                 cv.push_back({ i, j });                 map[i][j] = '.';             }         }     }     cout << bfs() << "\n"; } Colored by Color Scripter

cs

 

모르는 점이나 혹은 궁금한점 이있다면 언제든지

댓글을 이용해주시길 바랍니다