kangspa.com
출처 : 구슬 탈출 2
Solution
C
#define _CRT_SECURE_NO_WARNINGS
typedef struct Node {
int Rx, Ry, Bx, By;
int count;
char flag; //h==head(start), u==up, d==down, l==left, r==right, c==cannot move, t==tail(end)
struct Node* next;
}Node;
int result = 11;
void init(char** Board, int N, int M, Node* Ball) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (Board[i][j] == 'R') {
Ball->Ry = i;
Ball->Rx = j;
Board[i][j] = '.';
}
else if (Board[i][j] == 'B') {
Ball->By = i;
Ball->Bx = j;
Board[i][j] = '.';
}
}
}
Ball->count = 0;
Ball->flag = 'h';
Ball->next = NULL;
}
Node* create(Node* prev) {
Node* next;
next = (Node*)malloc(sizeof(Node));
next->Rx = prev->Rx;
next->Ry = prev->Ry;
next->Bx = prev->Bx;
next->By = prev->By;
next->count = prev->count + 1;
prev->next = next;
return(next);
}
void delete(Node* top) {
Node* tmp;
tmp = top;
top = top->next;
free(tmp);
}
void check_the_way(char** Board, Node* Ball);
void up(char** Board, Node* Ball) {
int R = 1, B = 1;
int c = 0;
Node* top = create(Ball);
while (R == 1 || B == 1) {
if (Board[top->Ry - 1][top->Rx] == '#' || (top->Ry - 1 == top->By && top->Rx == top->Bx))
R = 0;
if (Board[top->By - 1][top->Bx] == '#' || (top->By - 1 == top->Ry && top->Bx == top->Rx))
B = 0;
if (R == 1 || B == 1) c = 1;
if (top->Ry <= top->By) {
if (R == 1) top->Ry--;
if (B == 1) top->By--;
}
else if (top->By < top->Ry) {
if (B == 1) top->By--;
if (R == 1) top->Ry--;
}
if (Board[top->By][top->Bx] == 'O')
return;
if (Board[top->Ry][top->Rx] == 'O') {
if (top->count < result) result = top->count;
return;
}
}
if (c == 1) {
top->flag = 'u';
check_the_way(Board, top);
}
else if (c == 0) {
top->flag = 'c';
check_the_way(Board, top);
}
}
void down(char** Board, Node* Ball) {
int R = 1, B = 1;
int c = 0;
Node* top = create(Ball);
while (R == 1 || B == 1) {
if (Board[top->Ry + 1][top->Rx] == '#' || (top->Ry + 1 == top->By && top->Rx == top->Bx))
R = 0;
if (Board[top->By + 1][top->Bx] == '#' || (top->By + 1 == top->Ry && top->Bx == top->Rx))
B = 0;
if (R == 1 || B == 1) c = 1;
if (top->Ry >= top->By) {
if (R == 1) top->Ry++;
if (B == 1) top->By++;
}
else if (top->By > top->Ry) {
if (B == 1) top->By++;
if (R == 1) top->Ry++;
}
if (Board[top->By][top->Bx] == 'O')
return;
if (Board[top->Ry][top->Rx] == 'O') {
if (top->count < result) result = top->count;
return;
}
}
if (c == 1) {
top->flag = 'd';
check_the_way(Board, top);
}
else if (c == 0) {
top->flag = 'c';
check_the_way(Board, top);
}
}
void left(char** Board, Node* Ball) {
int R = 1, B = 1;
int c = 0;
Node* top = create(Ball);
while (R == 1 || B == 1) {
if (Board[top->Ry][top->Rx - 1] == '#' || (top->Rx - 1 == top->Bx && top->Ry == top->By))
R = 0;
if (Board[top->By][top->Bx - 1] == '#' || (top->Bx - 1 == top->Rx && top->By == top->Ry))
B = 0;
if (R == 1 || B == 1) c = 1;
if (top->Rx <= top->Bx) {
if (R == 1) top->Rx--;
if (B == 1) top->Bx--;
}
else if (top->Bx < top->Rx) {
if (B == 1) top->Bx--;
if (R == 1) top->Rx--;
}
if (Board[top->By][top->Bx] == 'O')
return;
if (Board[top->Ry][top->Rx] == 'O') {
if (top->count < result) result = top->count;
return;
}
}
if (c == 1) {
top->flag = 'l';
check_the_way(Board, top);
}
else if (c == 0) {
top->flag = 'c';
check_the_way(Board, top);
}
}
void right(char** Board, Node* Ball) {
int R = 1, B = 1;
int c = 0;
Node* top = create(Ball);
while (R == 1 || B == 1) {
if (Board[top->Ry][top->Rx + 1] == '#' || (top->Rx + 1 == top->Bx && top->Ry == top->By))
R = 0;
if (Board[top->By][top->Bx + 1] == '#' || (top->Bx + 1 == top->Rx && top->By == top->Ry))
B = 0;
if (R == 1 || B == 1) c = 1;
if (top->Rx >= top->Bx) {
if (R == 1) top->Rx++;
if (B == 1) top->Bx++;
}
else if (top->Bx > top->Rx) {
if (B == 1) top->Bx++;
if (R == 1) top->Rx++;
}
if (Board[top->By][top->Bx] == 'O')
return;
if (Board[top->Ry][top->Rx] == 'O') {
if (top->count < result) result = top->count;
return;
}
}
if (c == 1) {
top->flag = 'r';
check_the_way(Board, top);
}
else if (c == 0) {
top->flag = 'c';
check_the_way(Board, top);
}
}
void check_the_way(char** Board, Node* top) {
if (top->flag == 'c') {
delete(top);
return;
}
if (Board[top->Ry - 1][top->Rx] != '#' && top->flag != 'd')
up(Board, top);
else if (Board[top->Ry + 1][top->Rx] != '#' && top->flag != 'u')
down(Board, top);
else if (Board[top->Ry][top->Rx - 1] != '#' && top->flag != 'r')
left(Board, top);
else if (Board[top->Ry][top->Rx + 1] != '#' && top->flag != 'l')
right(Board, top);
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
getchar();
Node* Ball;
Ball = (Node*)malloc(sizeof(Node));
char** Board;
Board = (char**)calloc(N, sizeof(char*));
for (int i = 0; i < N; i++)
Board[i] = (char*)calloc(M, sizeof(char));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
scanf("%c", &Board[i][j]);
getchar();
}
init(Board, N, M, Ball);
check_the_way(Board, Ball);
printf("%d", result);
return 0;
}
'''GPT가 refactoring한 코드
#define MAX_N 10
#define MAX_M 10
// Define structure to hold game board state
typedef struct {
char cells[MAX_N][MAX_M];
int red_row, red_col, blue_row, blue_col;
} board_t;
// Define recursive function to solve game
int solve(board_t board, int last_move) {
// Check if current state is a winning or losing position
int red_in_goal = 0, blue_in_goal = 0;
for (int i = 0; i < MAX_N; i++) {
for (int j = 0; j < MAX_M; j++) {
if (board.cells[i][j] == 'R') {
if (i == board.red_row && j == board.red_col) {
red_in_goal = 1;
}
} else if (board.cells[i][j] == 'B') {
if (i == board.blue_row && j == board.blue_col) {
blue_in_goal = 1;
}
}
}
}
if (red_in_goal && !blue_in_goal) {
return 1; // Red ball in goal, game won
} else if (blue_in_goal || last_move == 10) {
return -1; // Blue ball in goal or too many moves, game lost
}
// Loop through possible directions
int directions[4][2] = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
for (int i = 0; i < 4; i++) {
// Simulate moving balls in this direction
int red_new_row = board.red_row + directions[i][0];
int red_new_col = board.red_col + directions[i][1];
int blue_new_row = board.blue_row + directions[i][0];
int blue_new_col = board.blue_col + directions[i][1];
// Check if red ball can move in this direction
if (board.cells[red_new_row][red_new_col] == '.') {
// Move red ball
board.cells[board.red_row][board.red_col] = '.';
board.cells[red_new_row][red_new_col] = 'R';
board.red_row = red_new_row;
board.red_col = red_new_col;
// Check if blue ball can move in this direction
if (board.cells[blue_new_row][blue_new_col] == '.') {
// Move blue ball
board.cells[board.blue_row][board.blue_col] = '.';
board.cells[blue_new_row][blue_new_col] = 'B';
board.blue_row = blue_new_row;
board.blue_col = blue_new_col;
// Check if resulting state is valid
int valid = 1;
if (red_new_row == blue_new_row && red_new_col == blue_new_col) {
if (i == 0) { // Up
valid = board.red_row < board.blue_row;
} else if (i == 1) { // Down
valid = board.red_row > board.blue_row;
} else if (i == 2) { // Left
valid = board.red_col < board.blue_col;
} else if (i == 3) { // Right
valid = board.red_col > board.blue_col;
}
if (!valid) {
// Move blue ball back
board.cells[board.blue_row][board.blue_col] = '.';
board.cells[blue_new_row - directions[i][0]][blue_new_col - directions[i][1]] = 'B';
board.blue_row -= directions[i][0];
board.blue_col -= directions[i][1];
}
}
// If resulting state is valid, recursively call function
if (valid) {
int result = solve(board, i);
if (result == 1) {
return 1;
}
}
}
// If blue ball cannot move, move red ball back
board.cells[board.red_row][board.red_col] = '.';
board.cells[red_new_row - directions[i][0]][red_new_col - directions[i][1]] = 'R';
board.red_row -= directions[i][0];
board.red_col -= directions[i][1];
}
}
// If none of the recursive calls returned a winning position, return -1
return -1;
}
int main() {
// Read input and initialize game board state
int n, m;
scanf("%d %d", &n, &m);
board_t board;
for (int i = 0; i < n; i++) {
scanf("%s", board.cells[i]);
for (int j = 0; j < m; j++) {
if (board.cells[i][j] == 'R') {
board.red_row = i;
board.red_col = j;
}
else if (board.cells[i][j] == 'B') {
board.blue_row = i;
board.blue_col = j;
}
}
}
printf(solve(board, 0));
return 0;
}
'''
Python
import sys
input = sys.stdin.readline
# 구슬 움직임 체크 함수
def move(x, y, dx, dy):
cnt = 0
# 못 움직이기 전까지 +1하면서 움직여준다
while board[y+dy][x+dx] != '#' and board[y][x] != 'O':
x += dx
y += dy
cnt += 1
return x, y, cnt
def bfs(rx, ry, bx, by):
# 각각 움직일 수 있는 좌표를 체크해둔다.
dx, dy = (-1, 0, 1, 0), (0, -1, 0, 1)
# 큐에 2 구슬의 좌표값과 카운트 값 같이 넣어둠
queue = []
queue.append((rx,ry,bx,by,0))
visited[rx][ry][bx][by] = True
while queue:
now = queue.pop(0)
# 10번 이상 움직이면 체크할 필요 없다.
if now[4] >= 10:
continue
# 2 구슬은 같은 방향으로 움직여야하니 4가지 방향에 대해서만 각각 체크해줌
for xd, yd in zip(dx,dy):
rx, ry, bx, by, cnt = now[0], now[1], now[2], now[3], now[4]
# 전부 움직였을 때 최종 위치와 각 구슬이 움직인 횟수 체크
rx, ry, rcnt = move(rx, ry, xd, yd)
bx, by, bcnt = move(bx, by, xd, yd)
cnt += 1
# 파란게 들어갔으면 안되니까 continue
if board[by][bx] == 'O':
visited[rx][ry][bx][by] = True
continue
# 빨간게 들어갔으면 그대로 움직인 횟수 반환
if board[ry][rx] == 'O':
visited[rx][ry][bx][by] = True
return cnt
# 만약 두 구슬이 같은 위치에 있을 때,
# 둘 중 더 많이 움직인걸 한칸 전 좌표로 바꿔준다.
if rx == bx and ry == by:
if rcnt > bcnt:
rx -= xd
ry -= yd
else:
bx -= xd
by -= yd
# 현재 두 구슬의 위치가 한번도 나온 적 없는 모양이라면 방문체크하고 큐에 넣는다.
if visited[rx][ry][bx][by] == False:
visited[rx][ry][bx][by] = True
queue.append((rx, ry, bx, by, cnt))
# 아무리 해도 통과 못하면 -1
return -1
if __name__ == '__main__':
n, m = map(int, input().split())
board = [list(input().strip()) for _ in range(n)]
# 두 구슬의 위치를 한번에 체크한다.
visited = [[[[False] * n for _ in range(m)] for _ in range(n)] for _ in range(m)]
# 빨간 구슬, 파란 구슬 위치 찾아서 따로 저장하고 . 으로 바꿔준다.
for y in range(n):
for x in range(m):
if board[y][x] == 'R':
rx, ry = x, y
board[y][x] = '.'
elif board[y][x] == 'B':
bx, by = x, y
board[y][x] = '.'
# bfs로 탐색하고 나온 값 출력
print(bfs(rx, ry, bx, by))
문제
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
출력
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
예제 입력 1
5 5 ##### #..B# #.#.# #RO.# #####
예제 출력 1
1
예제 입력 2
7 7 ####### #...RB# #.##### #.....# #####.# #O....# #######
예제 출력 2
5
예제 입력 3
7 7 ####### #..R#B# #.##### #.....# #####.# #O....# #######
예제 출력 3
5
예제 입력 4
10 10 ########## #R#...##B# #...#.##.# #####.##.# #......#.# #.######.# #.#....#.# #.#.#.#..# #...#.O#.# ##########
예제 출력 4
-1
예제 입력 5
3 7 ####### #R.O.B# #######
예제 출력 5
1
예제 입력 6
10 10 ########## #R#...##B# #...#.##.# #####.##.# #......#.# #.######.# #.#....#.# #.#.##...# #O..#....# ##########
예제 출력 6
7
예제 입력 7
3 10 ########## #.O....RB# ##########
예제 출력 7
-1