문제 풀이 1️⃣ 목표지점 2를 찾아서 위치를 저장해둡니다. 2️⃣ 1의 값들을 전부 -1로 바꿔줍니다. 3️⃣ 찾아놓은 목표지점 위치부터 시작해서 bfs 그래프 너비 탐색을 통해서 이동할 수 있는 부분들을 탐색합니다. 4️⃣ 전체 탐색하고 탐색하지 못한부분은 -1로 그대로놔둡니다. 5️⃣ arr에 저장되어있는 값을 출력형식에 맞게 출력합니다. 전체 코드 from sys import stdin as s from collections import deque s=open('input.txt','rt') # bfs 함수부분 def bfs(si,sj): q=deque() q.append((si,sj)) v[si][sj]=1 # 4방향 탐색위한 방향설정 dx=[0,1,0,-1] dy=[1,0,-1,0] while..

문제 풀이 1️⃣ 치킨집의 위치와 집의 위치를 미리 찾아서 리스트에 저장합니다. 2️⃣ 치킨집과의 최솟값을 찾아야하므로 변수를 max사이즈로 지정해줍니다. 3️⃣ M개수만큼의 치킨집을 골랐을 때 최솟값을 찾아야하므로 M개의 치킨집을 고르는 조합의 수를 구합니다. 4️⃣ 조합의 수를 구하기위해 브루트포스와 백트래킹 알고리즘을 사용합니다. 5️⃣ dfs 재귀를 반복하면서 조건에 충족됐을 때 집과 치킨집과의 거리를 저장합니다. 6️⃣ 저장한 치킨집과의 거리를 min함수로 저장해서 최솟값을 출력합니다. 전체 코드 from sys import stdin as s s=open('input.txt','rt') def dfs(cur,arr): global answer # arr의 길이가 M과 같으면 아래 조건문 진입 ..

풀이 방법 1️⃣ dfs를 통해서 문자를 백트래킹의 과정을 통해 구할 수 있는 모든 문자를 구합니다. 2️⃣ 문자들의 조합 중에서 모음이 최소한 한 개 이상 자음이 최소한 두 개이상이어야 하므로 만들어진 L크기의 문자를 확인합니다. 3️⃣ if문을 통해 정답으로 체크된 문자들이 모여있는 result 리스트를 출력형식에 맞게 출력합니다. 전체 코드 from sys import stdin as s s=open('input.txt','rt') L,C = map(int,s.readline().split()) arr=list(map(str,s.readline().split())) alpha=['a','e','i','o','u'] arr.sort() answer=[] result=[] def dfs(v, answe..

위 문제는 원하는 인원수를 최소 비용으로 구하는 방법을 요구하는 문제입니다. 제 풀이는 다이내믹 프로그래밍을 사용해서 풀었고 이 문제를 구현할 때는 "이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오." 문장을 잘 확인해야 합니다. 예제 2번같은 경우를 보면 dp [10]을 구해야 하지만 dp [3]=1 , dp [6]=2, dp [9]=3이 될 때 dp [10]은 4로 구해지는 것을 봤을 때 뒤에 부분까지 구하고 최솟값을 구한다고 생각하면 됩니다. 따라서 범위는 구하고자하는 C의 범위에 배열 arr의 최대 인원값을 더해준 범위까지 구한 것의 최솟값을 구하면 됩니다. 전체 코드 from sys import stdin as s s=open('i..

이 문제를 처음 봤을 때 정렬돼있는 부분과 입력값의 범위가 큰 것을 보고 그리디 알고리즘을 활용해야 하는 부분까지는 접근하였는데 아무리 생각해도 한번의 탐색을 통해 값을 구할 수 있는 방법을 찾지 못했습니다. 친구의 설명을 통해 문제에 대한 접근 방법을 알 수 있었고 DP와 그리디는 방법만 알면 구현하기는 정말 쉬운데 그 방법을 생각하는 과정이 어려운 것 같다. 우선 이 문제는 K개의 조가 1이라고 가정하면 1 3 5 6 10에서 (10-1)로 값은 9가 나온다. 하지만 K가 2라고 생각하면 2개의 조로 나눠야하는데 이때 (1 3 5 6) | (10)으로 나눈 값이 최솟값을 의미한다. 이는 앞 뒤의 차가 가장 큰 부분을 나누면 조를 나눴을 때 가장 큰 값을 갖게 된다는 것을 의미한다. 그래서 한번의 fo..

이 문제는 구현문제로 그래프 탐색과 더불어서 풀었습니다. 처음에는 미세먼지가 확산하는 부분까지는 기존 bfs문제들과 비슷해서 작성할 수 있었는데 이 문제에서는 공기청정기 윗 부분과 아랫 부분을 나눠서 한칸씩 밀려나가는 것을 구현하는 부분이 어려웠습니다. 머릿속으로는 벽에 부딪히면 방향을 전환하고 값들을 하나씩 이동시키는 형식으로 구현하면되겠다라고 생각은 드는데 막상 구현을 하자니 어디서부터 어떻게 구현해야하는지가 어려웠던 것 같습니다. R,C,T = map(int,s.readline().split()) arr = [list(map(int,s.readline().split())) for _ in range(R)] #로봇의 위치 저장하는 배열 machine=[] #미세먼지 누적 합 저장 result=0 #동..

문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이과정 이 문제는 그래프 탐색, bfs, 브루트 포스 알고리즘, 백트래킹 등 여러개의 알고리즘이 섞여있는 문제이다. 우선 어느 경우의 수에서 최대 안전 영역의 개수가 나오는지 모르기 때문에 모든 경우를 탐색하는 수 밖에 없다. 배열의 첫번째부터 벽을 세워나가서 벽의 개수가 3개가 됐을 때 bfs를 실행하고 바이러스를 전염 시키고 나서 안전 영역의 개수를 카운터해서 저장해놓고 제일 큰 값을 나중..

이 문제를 처음 봤을 때 지문을 잘못이해해서 왼쪽으로90도 회전하고 이동하고를 같은 자리를 무한 반복하는 줄 알았다.. 질문 게시판을 가보니 나와 같은 문제를 갖고 있는 사람들이 많아서 질문을 읽고 이해를 하게되었습니다. 우선 문제의 풀이방법을 생각해보면 dfs,bfs 방식으로 접근할 수 있고 제가 풀이한 방식은 dfs의 방식을 사용했습니다. N,M = map(int,s.readline().split()) r,c,d = map(int,s.readline().split()) cnt=0 #북동남서순서 dx=[-1,0,1,0] dy=[0,1,0,-1] arr = [list(map(int,s.readline().split())) for _ in range(N)] dfs(r,c,d) 처음 주어진 방향의 값이(d)..