www.acmicpc.net/workbook/view/1152 (A형 문제집)
BOJ 삼성 SW 기출문제 중 첫번째 문제이다.
예전엔 삼성 S 직군도 GSAT으로 입사했다가 SW 역량 테스트로 변경된 걸로 안다.
첫 번째 시험 치곤 난이도가 높은 편인 듯...
고려해야할 사항이 많고 디버깅도 쉽지 않다.
특히 2차원 맵 디버깅은 맵 전체를 printf로 찍어줘야하는 경우가 대부분이다.
이럴 때는 output.txt로 출력하는 설정을 해두는게 편하다.
1) 구슬이 1칸 움직이는 것이 아니라 멈출 때까지 움직여야 한다.
2) 최대 10번까지 도달하는 지만 검사하면 된다.
3) 빨간 구슬은 들어가고, 파란 구슬은 들어가면 안된다.
최소한의 경우를 맞춰야 하므로, 결국 모든 경우의 수를 다 따져보면 된다.
삼성 SW A형 문제 1개는 100% DFS나 BFS를 이용한 완전 탐색이다.
왼쪽, 오른쪽, 위쪽, 아래쪽 기울이는 경우는 4번,
총 10회 기울이므로, 410=1,048,576번, 즉 많아야 100만번 정도만 해보면 된다.
실제 시험에서는 50개의 test case를 1~10초 내로 통과해야하고, 1억 연산에 1초로 잡아서 계산하면 쉽다.
이 문제는 최악의 test case가 100만번 연산이 들어가므로 무조건 풀 수 있다.
만들어야 함수는 다음과 같다.
1) input값을 받아서 MAP을 만들어주는 함수.
2) 디버깅을 위한 map 출력 함수.
3) DFS, 재귀 함수로 구슬을 직접 움직이는 함수.
1), 2)는 본인 취향대로 하면 되므로 3번 함수를 설계해보자.
먼저 현재 구슬의 위치에서 4방향으로 움직일 수 있으므로 아래의 코드가 들어간다.
/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };
void DFS(...)
{
for (int i = 0; i < 4;i++)
{
// 4방향 움직이기.
// 현재 좌표 r, c => r + dr[i], c + dc[i]
}
// ...
}
2차원 좌표를 움직이는 것을 구현할 때는, dr, dc 배열을 선언해두면 좋다.
예를 들어, 현재 좌표가 (5, 3) 이라면 4방향 좌표는
5 + dr[0], 3 + dc[0] => (5, 2) 왼쪽 이동.
5 + dr[1], 3 + dc[1] => (4, 2) 위로 이동.
5 + dr[2], 3 + dc[2] => (5, 4) 오른쪽 이동.
5 + dr[3], 3 + dc[3] => (6, 2) 아래로 이동.
(참고로 수학 시간에 배운 좌표랑 헷갈리지 말자. 배열 기준 좌표로 (0, 0)이 가장 위쪽이면서 왼쪽이다.)
따라서 dr/dc 배열을 만들어주고, for문으로 4방향을 움직일 수 있다.
이제 DFS 함수의 parameter로 무엇이 필요한지 생각해보자.
DFS의 return 조건은 다음과 같다.
1) 10번 이상 움직였을 경우.
2) 빨간 구슬이 구멍에 빠진 경우.
빨간 구슬과 파란 구슬이 움직이므로 각 구슬의 좌표가 필요하고,
10번일 경우 종료해야 하므로, 깊이(Level)가 필요하다.
그리고 답을 기억할 변수 MIN을 적당히 큰 값으로 선언하자.
int MIN = 0x7FFF0000;
void DFS(int L, int Rr, int Rc, int Br, int Bc) /* Red row, Red column, ... */
{
if (L > 10) return;
...
if (/* RED가 구멍에 빠진 경우*/)
{
if(L < MIN) MIN = L;
}
}MIN은 전역변수로 해두면 편하다.
실제 SW 시험에서는 tc를 여러번 돌리므로 매 tc마다 MIN = 0x7FFF0000으로 초기화 하는 것을 잊지 말자.
이제 구슬 2개의 좌표도 받았고, 4방향으로 움직이는 것도 구현하였으니, 실제 움직이는 코드를 구현해보자.
왼쪽으로 이동하는 경우, 현재 빨간, 파란 구슬의 좌표에서 dr[0]과 dc[0]을 계속 더해주면 된다.
그럼 언제까지 더해줘야할까?
두 구슬이 모두 움직일 수 없을 때 까지 더해 줘야한다.
즉, while(1)을 걸어둔 다음, 두 구슬의 다음 좌표가 '#'(벽)이면 break를 하자.
이때, 한 구슬이라도 움직이면 계속 해야하므로, 4개의 경우로 나눌 수 있다.
1) 모든 구슬이 움직이는 경우. => 구슬의 다음 좌표가 모두 벽인 경우.
2) 빨간 구슬이 멈춘 경우. => 파란 구슬의 다음 좌표가 벽이 아니고, 빨간 구슬도 아닌 경우.
3) 파란 구슬이 멈춘 경우. => 빨간 구슬의 다음 좌표가 벽이 아니고, 파란 구슬도 아닌 경우.
4) 모두 움직일 수 없는 경우.
1)에서는 다른 구슬의 좌표를 생각할 필요가 없다.
두 구슬 중 먼저 멈추는 구슬은 반드시 벽 때문에 멈춘다.
보드를 기울이면 같은 방향으로 기울기 때문이다.
코드는 다음과 같다.
for (int i = 0; i < 4;i++)
{
int nr, nc, mr, mc;
nr = Rr; nc = Rc; mr = Br; mc = Bc;
while (1)
{
/* 모두 벽이 아닌 경우 */
if (MAP[nr + dr[i]][nc + dc[i]] != '#'
&& MAP[mr + dr[i]][mc + dc[i]] != '#')
{...}
/* Red가 벽이고, Blue는 움직일 수 있는 경우 */
else if (MAP[nr + dr[i]][nc + dc[i]] == '#'
&& (MAP[mr + dr[i]][mc + dc[i]] != '#' && !(mr + dr[i] == nr && mc + dc[i] == nc)))
{...}
/* Blue가 벽이고, Red는 움직일 수 있는 경우 */
else if (MAP[mr + dr[i]][mc + dc[i]] == '#'
&& (MAP[nr + dr[i]][nc + dc[i]] != '#' && !(nr + dr[i] == mr && nc + dc[i] == mc)))
{...}
/* 둘 다 움직일 수 없는 경우 */
else
break;
}
DFS(L + 1, nr, nc, mr, mc); /* 구한 좌표로 다음 기울이기 시작 */
}
이제 각 경우에 대해 답을 찾아보자.
1) 모든 구슬이 움직이는 경우.
빨간 구슬의 좌표가 '0' 이면 종료... 라고 생각하면 예제만 통과하고 헤매게 된다.
파란 구슬을 계속 움직여서 '0'이 아닌지 체크해야된다.
만약에 '0'이 되는 경우 셀 필요가 없으므로, 파란 구슬이 '0'이 었는지 체크하는 flag를 두자.
2) 빨간 구슬이 멈춘 경우.
파란 구슬을 움직이면서 '0'인지 체크, '0'이 된다면 더이상 움직일 필요 없으므로 종료.
3) 파란 구슬이 멈춘 경우.
빨간 공이 '0'이 되는지 체크, '0'이 된다면 MIN을 갱신하고 종료.
4) 모두 움직일 수 없는 경우.
break; 후 갱신된 좌표로 DFS 재시작. 현재의 Level + 1을 넘겨서 현재 depth를 기억
전체 코드는 다음과 같다.
#include <stdio.h>
#define MAX (10 + 5)
int N, M;
char MAP[MAX][MAX];
typedef struct st
{
int r;
int c;
}BALL;
BALL RED;
BALL BLUE;
int dr[] = { 0,-1,0,1 };
int dc[] = { -1,0,1,0 };
void input(void)
{
scanf("%d %d", &N, &M);
for (int r = 0; r < N;r++)
{
for (int c = 0;c < M;c++)
{
scanf(" %c", &MAP[r][c]);
if (MAP[r][c] == 'R')
{
RED.r = r;
RED.c = c;
}
if (MAP[r][c] == 'B')
{
BLUE.r = r;
BLUE.c = c;
}
}
}
}
int MIN = 0x7FFF0000;
void DFS(int L, int Rr, int Rc, int Br, int Bc)
{
if (L > 10) return;
for (int i = 0; i < 4;i++)
{
int FLAG = 0;
int nr, nc, mr, mc;
nr = Rr; nc = Rc; mr = Br; mc = Bc;
while (1)
{
if (MAP[nr + dr[i]][nc + dc[i]] != '#' && MAP[mr + dr[i]][mc + dc[i]] != '#')
{
nr += dr[i]; nc += dc[i];
mr += dr[i]; mc += dc[i];
if (MAP[nr][nc] == 'O')
{
int flag = 0;
while (MAP[mr][mc] != '#')
{
if (MAP[mr][mc] == 'O')
{
flag = 1;
break;
}
mr += dr[i];
mc += dc[i];
}
if (flag) break;
else
{
if (MIN > L) MIN = L;
return;
}
}
if (MAP[mr][mc] == 'O')
{
FLAG = 1;
break;
}
}
else if (MAP[nr + dr[i]][nc + dc[i]] == '#'
&& (MAP[mr + dr[i]][mc + dc[i]] != '#' && !(mr + dr[i] == nr && mc + dc[i] == nc)))
{
mr += dr[i];
mc += dc[i];
if (MAP[mr][mc] == 'O')
{
FLAG = 1;
break;
}
}
else if (MAP[mr + dr[i]][mc + dc[i]] == '#'
&& (MAP[nr + dr[i]][nc + dc[i]] != '#' && !(nr + dr[i] == mr && nc + dc[i] == mc)))
{
nr += dr[i];
nc += dc[i];
if (MAP[nr][nc] == 'O')
{
if (MIN > L) MIN = L;
return;
}
}
else break;
}
if (FLAG == 0) DFS(L + 1, nr, nc, mr, mc);
}
}
int main(void)
{
input();
DFS(1, RED.r, RED.c, BLUE.r, BLUE.c);
if (MIN == 0x7FFF0000) printf("-1\n");
else printf("%d\n", MIN);
return 0;
}
실제 알고리즘 시험에서는 tc가 여러 개이므로 다음과 같이 작성해줘야 한다.
int main(void)
{
int T;
scanf("%d", &T);
for (int tc = 1; tc <= T; tc++)
{
MIN = 0x7FFF0000;
input(); // + 초기화 코드 추가
DFS(1, RED.r, RED.c, BLUE.r, BLUE.c);
if (MIN == 0x7FFF0000) printf("#%d -1\n", tc);
else printf("#%d %d\n", tc, MIN);
}
return 0;
}
MIN을 초기화한 것처럼, input 내부에도 초기화 코드를 꼭 추가해두자.
SW TEST에서는 초기화를 안해서 시간을 날려먹는 경우가 많다.
마지막으로 최적화 코드를 추가하자.
현재 DFS 코드는 왼쪽으로 보드를 기울였다면, 다음 Level에서도 왼쪽으로 기울이게 된다.
다음 Level로 넘어 갔다는 뜻은 왼쪽으로 기울였을 때, 움직일 수 있는 공이 없다는 뜻이다.
따라서, while 시작 전에, 다음 좌표가 둘다 벽이면 continue 해주는 코드를 넣어주자.
for (int i = 0; i < 4;i++)
{
int FLAG = 0;
int nr, nc, mr, mc;
nr = Rr; nc = Rc; mr = Br; mc = Bc;
/* 움직이기 전에 벽인지 체크 */
if (MAP[nr + dr[i]][nc + dc[i]] == '#'
&& MAP[mr + dr[i]][mc + dc[i]] == '#') continue;
while (1)
{...}
...
}
최적화 코드를 추가하면 20ms -> 4ms로 줄어든다.
아마 시험 난이도가 어려워서, 최적화까지는 필요 없을 수도...
'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글
| BOJ 14499 : 주사위 굴리기 (삼성 SW TEST A형) (0) | 2021.02.15 |
|---|---|
| BOJ 13458 : 시험 감독 (삼성 SW TEST A형) (0) | 2021.02.15 |
| BOJ 3190 : 뱀 (삼성 SW TEST A형) (0) | 2021.02.14 |
| BOJ 12100 : 2048 Easy (삼성 SW TEST A형) (0) | 2021.02.07 |
| 백준에서 삼성 SW 기출 문제 보는 방법 (0) | 2021.02.06 |
댓글