ajaaCoding

📌문제예제 5-11 미로 탈출동빈이는 N x M 크기의 직사각형 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한칸씩 이동할 수 있다.괴물이 있는 부분은 0, 괴물이 없는 부분은 1이다.이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 📌풀이(1, 1) 지점에서부터 BFS 수행시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색 📌코드from collections import dequen, m = map(int, input().split())# 2차원 리스트의 맵 정보 입력받기graph = []for i in range(n): graph.appe..

📌문제예제 5-10 음료수 얼려 먹기 문제N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 📌풀이얼음틀을 그래프 형태로 모델링하여 DFS로 해결1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에 값이 0이면서 아직 방문하지 않은 지점이 있다면 방문2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행3. 1~2번 과정을 모든 노드에 반복하여 방문하지 않은 지점의 수를 셈 📌코드n, m = map(int, ..

📌BFS너비 우선 탐색 (Breadth First Search)가까운 노드부터 탐색하는 알고리즘 BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석인접한 노드를 반복적으로 큐에 넣도록하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색 진행 📌BFS 동작 방식1. 탐색 시작 노드를 큐에 삽입하고 방문 처리2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복  📌BFS 코드from collections import dequedef bfs(graph, start, visited): #큐 구현을 위해 deque 라이브러리 사용 queue=deque([..

📌DFSDepth-First-Search깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 📌그래프 표현 방식1. 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식2. 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식  위 그래프를 각 방식으로 표현한다면 다음과 같다 📌인접 행렬 방식2차원 배열에 각 노드가 연결된 형태를 기록하는 방식파이썬에서는 배열을 리스트 자료형으로 표현할 수 있으므로 인접행렬을 리스트로 구현함INF = 99999999 # 무한의 비용 선언# 2차원 리스트를 이용해 인접 행렬 표현graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0]]print(graph) 연결되어 있지 않은 노드끼..

📌재귀함수자기 자신을 다시 호출하는 함수DFS와 BFS를 구현하려면 재귀함수도 이해해야 함 📌재귀함수 코드def recursive_function(): print("재귀함수를 호출합니다.") recursive_function()recursive_function() 📌재귀함수의 종료 조건재귀함수의 종료 조건을 꼭 명시해야 함자칫 종료 조건을 명시하지 않으면 함수가 무한 호출 될 수 있음 📌코드def recursive_function(i): # 100번째 출력했을 때 종료되도록 종료 조건 명시 if i == 100: return print(i, "번째 재귀 함수에서", i + 1, "번째 재귀 함수를 호출합니다.") recursive_function(i +..

📌탐색많은 양의 데이터 중에서 원하는 데이터를 찾는 과정보통 그래프, 트리 등의 자료구조 안에서 탐색 📌탐색 알고리즘DFS, BFS이를 이해하기 위해서는 먼저 기본 자료구조인 스택, 큐에 대해 이해해야 함 📌오버플로, 언더플로오버플로: 자료구조에 데이터가 이미 가득 찬 상태에서 삽입 연산을 할 때 발생언더플로: 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 할 때 발생 📌스택박스 쌓기처럼 아래에서부터 위로 차곡차곡 쌓는 구조선입후출(First In Last Out) , 후입선출(Last In First Out) 구조 파이썬에서 스택을 이용할 때 별도의 라이브러리 사용할 필요 없음기본 리스트에서 append()와 pop() 메서드 사용 append(): 리스트의 가장 뒤쪽에 데이터 삽..

📌문제예제 4-4 게임 개발게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고 바다는 갈 수 없다. 매뉴얼1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면..

📌문제예제 4-3 왕실의 나이트8 x 8 체스판에 나이트가 서 있다. 나이트는 이동을 할 때 L자 형태로만 이동할 수 있으며 체스판 밖으로는 나갈 수 없다.1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.이때 좌표의 행 위치를 표현할 때는 1~8로 표현하고, 열 위치를 표현할 때는 a~h로 표현한다. 📌풀이나이트의 이동 경로를 steps 변수에 넣는다면steps=[(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)] 나이트의 현재 위치가 주..

📌문제예제 4-2 시각 문제정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 📌풀이3중 반복문(시, 분, 초)을 사용하여 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인 00시 00분 00초부터 1초씩 늘리며 시, 분, 초를 문자열 자료형으로 변환하여 합침합친 문자열에 '3'이 포함되어 있는지 검사 📌코드h = int(input())count = 0for i in range(h + 1): # 0시 ~ h시 for j in range(60): # 0분 ~ 59분 for k in range(60): # 0초 ~ 59초 # 매 시각 안에 '3'이..

📌구현완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 유형 📌문제예제 4-1 상하좌우여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위의 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가는 상(U), 하(D), 좌(L), 우(R) 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. L, R, U, D로 이루어진 문자들이 적혀진 계획서를 보고 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.(단, N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.) ..