본문 바로가기

Algorithm/Problem Solving6

[Problem Solving] 음료수 얼려 먹기 이번에는 DFS와 BFS의 개념을 활용해 풀어야 하는 문제인 "음료수 얼려 먹기" 알고리즘 문제를 풀어보겠습니다. 문제 : N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총아이스크림의 개수를 구하는 프로그램을 작성하시오. 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로길이 M이 주어진다. (1 2021. 2. 4.
[Problem Solving] 게임 개발 문제 : 게임 개발 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터느 동서남북 중 한곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방.. 2021. 2. 2.
[Problem Solving] 왕실의 나이트 문제 : 왕실의 나이트 행복 왕국의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 말을 타고 있으므로 이동을 할 때는 L자 형태로만 이동가능하고 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 2. 수직으로 두 칸 이동한 두에 수평으로 한 칸 이동하기 이처럼 8 x 8 좌표 평명상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 구하여라. 행 위치의 표현은 1부터 8로 표한하고, 열 위치를 표현할 때는 a부터 h로 표현한다. 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문.. 2021. 2. 1.
[Problem Solving] 상하좌우 이번에는 구현에 대한 알고리즘을 공부하였다. 구현 알고리즘 "상하좌우"에 들어가기에 앞서 간단한 사방 탐색으로 시작해볼까 한다. 아래의 코드는 순서대로 우, 상, 좌, 하 순서대로 1, 2, 3, 4를 차례대로 채우는 예제이다. 특히 2차원 배열을 초기화할 때는 반드시 리스트 컴프리 헨션을 이용해 주어야 한다. 그렇지 않으면 데이터를 넣거나 하는 등의 과정에서 문제가 생길 수 있다. n = 3 m = 3 array = [[0] * m for _ in range(n)] # 리스트 컴프리 헨션을 이용한 2차원 배열 초기화 # 방향 벡터 이용 dx = [0, -1, 0, 1] # 행, row dy = [1, 0, -1, 0] # 열, column x, y = 1, 1 # 3 X 3 크기의 2차원 배열에서 1,.. 2021. 2. 1.

티스토리툴바