코딩테스트2 [BOJ 3190 파이썬] 뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은.. 2022. 6. 28. [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 의 개념과 차이 알고리즘을 풀다보면 그래프를 탐색해야하는 상황이 많이 발생한다. 그래프를 탐색하는 방법에는 크게 깊이 우선 탐색 (DFS)과 너비 우선 탐색 (BFS)가 있다. 두개의 알고리즘을 그림으로 보면 다음과 같다. 1. 깊이 우선 탐색 (DFS) ✅ 깊이 우선 탐색의 개념 한 노드로 부터 시작해서 다음 분기(다른 경로)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 예를 들어서, 미로찾기를 한다고 가정해보자. 최대한 한 방향으로 가다가 해당 방향의 막다른 길에 다다랐을때, 다시 갈림길로 돌아와서 다른 경로를 똑같이 탐색하고, 이를 탈출구를 찾을 때까지 반복하는 것이 바로 DFS 깊이 우선 탐색이다. 그런데, 만약 잘못 선택한 경로가 올바른 경로에 비해 매우 깊은 (시간이 많이 걸리는) 경로라면?.. 2022. 6. 27. 이전 1 다음
