우기의 알 블로그 저자 한승욱이라고 합니다.
스스로 알을 깨고 나오는 새처럼
언젠가 알을 깨고 온전한 나 자신이 되었을 때, 그때를 기다리며 제 속에서 솟아 나오는 것을 글로써 표현하고자 합니다.
'개발 기술블로그'를 위주로 저 한승욱의 다양한 관심사, 생각, 철학 등을 포스팅합니다.
game_map =[["#","#","#","#","#"],["#",".",".","B","#"],["#",".","#",".","#"],["#","R","O",".","#"],["#","#","#","#","#"],]# -> True를 반환해야 한다.
game_map =[["#","#","#","#","#","#","#","#","#","#"],["#","R","#",".",".",".","#","#","B","#"],["#",".",".",".","#",".","#","#",".","#"],["#","#","#","#","#",".","#","#",".","#"],["#",".",".",".",".",".",".","#",".","#"],["#",".","#","#","#","#","#","#",".","#"],["#",".","#",".",".",".",".","#",".","#"],["#",".","#",".","#",".","#",".",".","#"]["#",".",".",".","#",".","O","#",".","#"],["#","#","#","#","#","#","#","#","#","#"]]# -> False 를 반환해야 한다
# 코드 스니펫from collections import deque
game_map =[["#","#","#","#","#"],["#",".",".","B","#"],["#",".","#",".","#"],["#","R","O",".","#"],["#","#","#","#","#"],]defis_available_to_take_out_only_red_marble(game_map):# 구현해보세요!returnprint(is_available_to_take_out_only_red_marble(game_map))# True 를 반환해야 합니다
문제 해결의 규칙성을 찾기 힘들기에 탐색하는 방법을 탐색해 나가야 하는데 이동할 수 있는 방향이
4개나 됨.
모든 경우를 시도해보면서 탈출할 수 있는 경우로 문제를 풀어야함.
즉, BFS를 이용하기로 함
# from collections import deque
game_map =[["#","#","#","#","#"],["#",".",".","B","#"],["#",".","#",".","#"],["#","R","O",".","#"],["#","#","#","#","#"],]# 위치
dr =[-1,0,1,0]
dc =[0,1,0,-1]# 방문 저장 여부 visited를 만들어야 함# 공이 2개 이라 4차원 배열을 사용!# visited[red_marble_row][red_marble_col][blue_marble_row][blue_marble_col]# 4차원 배열이 공간낭비가 아닐까 생각이 들지만 보드의 행 열 길이가 3 <= x <= 10 이기에 문제 없음!defmove_until_wall_or_hole(r, c, diff_r, diff_c, game_map):# game_map도 받는 이유는 이동하려는 곳이 벽인지 구멍인지 알아야 하기 때문에
move_count =0while game_map[r + diff_r][c + diff_c]!="#"and game_map !="0":# 이동할 곳이 벽이 아닐때까지와 구멍일때
r += diff_r
c += diff_c
move_count +=1return r, c, move_count
defis_available_to_take_out_only_red_marble(game_map):
n, m =len(game_map),len(game_map[0])
visited =[[[[False]* m for _ inrange(n)]for _ inrange(m)]for _ inrange(n)]# row 는 n, col은 m 즉 n, m, n, m 이기에 그 순서대로 초기화# print(visited)
red_row, red_col, blue_row, blue_col =-1,-1,-1,-1
queue = deque()for i inrange(n):for j inrange(m):if game_map[i][j]=="R":
red_row, red_col = i, j
elif game_map[i][j]=="B":
blue_row, blue_col = i, j
# 탐색을 10번까지만 할 수 있음
queue.append((red_row, red_col, blue_row, blue_col,1))
visited[red_row][red_col][blue_row][blue_col]=True# 큐룰 이용한 탐색while queue:
red_row, red_col, blue_row, blue_col, try_count = queue.popleft()if try_count >10:break# 이동에 대한 모든 경우for i inrange(4):
next_red_row, next_red_col, r_count = move_until_wall_or_hole(red_row, red_col, dr[i], dc[i], game_map)
next_blue_row, next_blue_col, b_count = move_until_wall_or_hole(blue_row, blue_col, dr[i], dc[i], game_map)if game_map[next_blue_row][next_blue_col]=='O':continue# 블루가 먼저 들어갔기에if game_map[next_red_row][next_red_col]=='O':returnTrue# 레드가 먼저 들어갔다면# 블루와 레드는 만날 수가 없음 끝까지 가는 도중에 동일 선상에 있으면 안됨# ..BR 일때 다 왼쪽 끝으로 옮기면# B..# R# 이런 구조가 되는데 이렇게 되면 안되기에 BR..으로 되야함. 옮긴 다음에 후보정을 해줘야함# 벽에 다다랐을때 두개의 움직은 거리를 비교해서 조금 움직인애는 그대로 끝에 있고 더 많이 움직인애는 한칸 떨어지게 함# 위의 예에서 B는 2번 이동, R은 3번 이동if next_red_row == next_blue_row and next_red_col == next_blue_col:if r_count > b_count:
next_red_row -= dr[i]
next_red_col -= dc[i]else:
next_blue_row -= dr[i]
next_blue_col -= dc[i]# BFS 방식이기에 현재 방문하지 않았다면 해당 위치를 다시 큐에 넣고 반복ifnot visited[next_red_row][next_red_col][next_blue_row][next_blue_col]:
visited[next_red_row][next_red_col][next_blue_row][next_blue_col]=True
queue.append((next_red_row, next_red_col, next_blue_row, next_blue_col, try_count +1))returnFalseprint(is_available_to_take_out_only_red_marble(game_map))# True 를 반환해야 합니다
알고리즘 실전 - 삼성 역량 테스트 - 2
구슬 탈출
문제 해결의 규칙성을 찾기 힘들기에 탐색하는 방법을 탐색해 나가야 하는데 이동할 수 있는 방향이 4개나 됨.
모든 경우를 시도해보면서 탈출할 수 있는 경우로 문제를 풀어야함.
즉, BFS를 이용하기로 함
'기술개발 > Algorithm' 카테고리의 다른 글