728x90 반응형 알고리즘 공부69 [BOJ] 7562번 나이트의 이동 / 사용언어 : 파이썬(python) ※ 문제링크 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 해당문제는 BFS를 활용하여 풀 수 있는 문제로, deque를 활용하여 BFS를 구현하여 해결을 하였다. 체스의 나이트의 이동조건을 알고 있는 사람이라면 보다 쉽게 해결할 수 있는 문제로 방문한 위치를 기록하고 목표점에 도달했을때에 반복문을 종료하는 방식으로 해결할 수 있었다. 자세한 문제풀이와 코드는 아래와 같다. 1. 입력받은 값을 바탕으로 반복문을 작성하고, 체스판을 작성하여 출발점만 1로 표기해준다. 2. 나이트의 최초위치와 목표점과 같을때에는.. 2022. 1. 10. [BOJ] 1697번 숨바꼭질 / 사용언어 : 파이썬(python) ※ 문제링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해당 문제는 BFS를 활용하여 풀 수 있는 문제였다. BFS 구현을 위해 collections의 deque를 사용하였으며, 문제에서 주어진 이동조건을 구현하기 위해 간단하게 함수를 작성하였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 N값을 deque리스트에 삽입하여주고, 이미 방문한 숫자들을 제외하기위해 방문여부를 확인할 배열을 작성해준다. 2. 이동할 수 있는 경우는 기본적으로 3개이기에 deque활용하여 .. 2022. 1. 10. [BOJ] 7576번 토마토 / 사용언어 : 파이썬(python) ※ 문제링크 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 해당문제는 BFS를 활용하여 풀 수 있는 문제였다. BFS를 구현하기 위해 파이썬에 내장되어 있는 collections의 deque를 사용했다. 기존의 문제들과 조금 차별점이 있다면 시작점이 1개가 아니라 여러개가 될 수 있다는 점이었기에 해당 부분에 초점을 두고 문제를 해결하였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 2차원 리스트 형태로 변환한다. 2. 배열의 처음부터 마지막까지 2중 반복문을 이용하여 탐색.. 2022. 1. 9. [BOJ] 2178번 미로 탐색 / 사용언어 : 파이썬(python) ※ 문제링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 해당 문제는 BFS를 활용하여 풀 수 있는 문제였다. DFS를 메모이제이션을 활용하여 기록하면서 풀면 답을 구할 수는 있으나, 시간 및메모리가 과도하게 사용되기에 BFS로 해결하기로 생각하였다. 문제조건 중 무조건 탈출이 가능하다는 전제조건이 주어졌기에 BFS함수를 작성하고 시작점에서 함수를 한번만 실행하는 방식으로 해결하였다. 자세한 문제풀이방법과 코드는 아래와 같다. 1. 입력받은 값을 2차원 배열로 변환하여 준다. 2. 파이썬 내장함수인 dequ.. 2022. 1. 7. [BOJ] 1012번 유기농 배추 / 사용언어 : 파이썬(python) ※ 문제링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해당문제는 DFS와 BFS를 사용하여 해결할 수 있는 문제였다. 단순하게 상, 하, 좌, 우에 연결되어 있는 배추의 위치들을 활용하여 연결된 그래프의 수가 몇개인지 구하면 되는 문제였기에 크게 어렵지 않게 해결할 수 있었다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값을 바탕으로 2차원 배열로 배추밭을 구현한다. 2. DFS 또는 BFS를 사용하여 연결된 배추들을 확인할 함수를 작성한다. 3. 2중 반복문을 활용하여 배추밭의 모든 위치를 확인하고, .. 2022. 1. 6. [BOJ] 2667번 단지번호 붙이기 / 사용언어 : 파이썬(python) ※ 문제링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 해당문제는 DFS와 BFS를 활용하여 풀 수 있는 문제였다. 조건은 간단하여 풀이방법을 떠올리는 것은 그리 어렵지 않았으나, 구현하는난이도가 생각보다 어려워서 꽤나 시간이 걸린 문제였다. 풀이방법에 대해 간단하게 이야기하면, 입력받은 문자열을 2차원 배열로 변환한 후, 배열 상 값이 1인 경우에 한하여 DFS 또는 BFS를 활용하여 해당 점을 기준으로 상, 하, 좌, 우를 확인하여 조건 충족하면 계속 탐색하여 결과를 작성하는 방식으로 해결하였다. 자세.. 2022. 1. 6. [BOJ] 2606번 바이러스 / 사용언어 : 파이썬(python) ※ 문제링크 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 해당문제는 DFS 또는 BFS로 해결할 수 있는 문제였다. 두가지방법 모두 사용하는 방법을 숙달하기 위해서 두가지 방법을 모두 이용해서 코드를 작성해보았고, 그래프는 딕셔너리를 이용하여 구현하였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력값을 반복문과 딕셔너리를 활용하여 그래프 형태로 변환한다. 2. dfs와 bfs함수를 작성하여 연결되어 있는 노드의 개수를 확인하고 결과값을 출력한다. + 처음에 작성한 코드는 dfs는 통과가 되었으나 bfs가 .. 2022. 1. 5. [BOJ] 1260번 DFS와 BFS / 사용언어 : 파이썬(python) ※ 문제링크 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ※ 관련개념 및 참고사이트 [Daily PS] 파이썬으로 구현하는 BFS와 DFS 파이썬으로 BFS와 DFS를 구현하는 내용입니다. cyc1am3n.github.io 해당 문제는 BFS와 DFS를 구현하는 문제였다. 문제를 풀기 전 개념에 대한 이해를 위해 구글링을 하던 중 설명이 잘 되어 있는 사이트가 있어서 해당 사이트를 참고하여 구현해보았다. 문제해결을 위해서는 먼저 입력값을 그래프 형태로 만들어주는 것이 .. 2022. 1. 5. [BOJ] 1759번 암호만들기 / 사용언어 : 파이썬(python) ※ 문제링크 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 해당문제는 DFS와 백트래킹을 일부 변형해서 풀 수 있는 문제였다. 문제 조건중 모음(1개이상)과 자음(2개이상) 최소개수가 주어졌기에 해당 조건을 추가시켜서 풀었더니 금방 풀 수 있었고, 정상적으로 작동하는 것을 확인했다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 변수로 할당해주고, 알파벳은 리스트로 변환 후 내장함수를 활용하여 정렬해준다. 2. 알파벳의 모음, 자음여부를 판단할 변수들을 만들고 값을 할당한다. 3. 시작값과 모음갯수.. 2022. 1. 4. 이전 1 ··· 4 5 6 7 8 다음 728x90 반응형
