코딩 대장

문제 풀이

 게임의 규칙을 찾아야 풀이가 가능한 문제입니다. 게임의 규칙은 다음과 같습니다.

1. 같은 곳을 두 번 뒤집으면 결과가 같으므로 이러한 경우는 고려하지 않아도 됩니다.

2. N은 짝수이므로,

2-1) (x, y)의 돌 (=노란색 별) 을 뒤집으면 자기 자신과 가로줄, 세로줄의 돌 색이 바뀌게 되므로 노란색 별 기준 주변의 검은색 돌 갯수는 홀수개가 됩니다.

2-2) 초록색 별 기준 바뀌는 돌의 색은 자기 자신과 자기 자신이 속한 한 줄이 되므로 검은 돌의 갯수는 짝수개가 됩니다.

2-3) 자기 자신의 색이 바뀌지 않는 빨간색 별 기준 바뀌는 돌의 색은 가로 줄 한 개, 세로 줄 한 개이므로 검은 돌의 갯수는 홀수개가 됩니다.

(+ 흰 색 돌을 기준으로 보는 경우 뒤집은 돌의 주변 흰색 돌만 짝수개가 됩니다.)

3. 즉, 가로줄의 검은 돌 갯수와 세로 줄의 검은 돌 갯수를 합한 것이 홀수라면, 뒤집은 돌이 됩니다. (중복 제외)

(+ cin, cout으로 받으면 시간 초과납니다ㅠㅠ)

코드

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

#include <iostream>   using namespace std;   int main() {       ios_base::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);          int t;     cin >> t;       for (int tc = 1; tc <= t; tc++)     {         int ans = 0;         char board[1000][1000];         int h[1000] = { 0, };         int v[1000] = { 0, };           int n;         cin >> n;           for (int i = 0; i < n; i++)         {             for (int j = 0; j < n; j++)             {                 cin >> board[i][j];                 if (board[i][j] == 'B')                 {                     h[i]++;                     v[j]++;                 }             }         }           for (int i = 0; i < n; i++)         {             for (int j = 0; j < n; j++)             {                 int x = h[i] + v[j];                 if (board[i][j] == 'B')                     x -= 1;                   if (x % 2 != 0)                     ans++;             }         }         cout << '#' << tc << ' ' << ans << '\n';     }     return 0; } http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWefzFeq5P8DFAUh&categoryId=AWefzFeq5P8DFAUh&categoryType=CODE

문제 풀이

 bfs 알고리즘을 활용하여 방문하지 않은 길을 따라 도착점이 나올 때까지 탐색하였습니다.

코드

제출 결과

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE&&&

풀이 과정

 arr에 map을 입력 받고, 시작점인 (0, 0)부터 탐색을 시작합니다. 해당 칸까지 이동하였을 때, 걸린 최소 비용을 dist 배열에 저장해 줍니다. dist 배열은 매우 큰 수로 초기값을 정해 줍니다. 

 간단한 예를 들어, dist에 파란색 경로의 최소 비용이 저장되어 있을 때, 주황색 경로의 최소 비용이 더 작은 경우 dist에 저장된 값을 주황색 경로의 값으로 갱신하여 줍니다. 따라서 탐색이 종료되면, dist[n-1][n-1]에는 (n-1, n-1)까지 가는 최소 비용이 저장되어 있게 됩니다.

코드

제출 결과

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&&&