https://www.acmicpc.net/problem/7576상하좌우의 토마트를 익힌다는 말을 보고 BFS를 떠올렸다.하지만 1. 날짜를 어떻게 카운트할 것인가, 2. 모든 토마토를 익히지 못하는 경우를 어떻게 알것인가이 두가지를 해결하지 못해서 찾아봤다.아이디어는 간단했다. 주변 토마토를 익히면 해당 위치의 값을 이전 위치의 값에 +1을 해주면 된다.이후 마지막에 순회하며 가장 큰 값을 찾은 뒤 -1을 하면 최종 걸리는 날짜를 구할 수 있다.또한 순회 중 익지 않은 토마토를 찾게 되면 -1을 출력하면 되는 간단한 생각이었다.from collections import dequem, n = map(int, input().split())tomato = []q = deque()for i in range(n..

https://www.acmicpc.net/problem/10971처음에는 최소 비용이라는 단어만 보고 무작정 BFS로 풀었다가 시간 초과로 못푼 문제.DFS로 순회를 하며 지금까지의 최소 비용보다 비용이 높다면 다시 그 전으로 돌아가 백트래킹을 하여 문제를 해결하였다.순회가 종료되었음을 확인하는 조건을 생각해내지 못해서 검색을 통해 풀었다.끝까지 순회를 한 뒤 마지막 지점에서 다시 출발 점으로 갈 수 있는지 확인하면 되는 간단한 방법이었다...DFS에 좀 더 익숙해져야 할 필요가 있다.from collections import dequen = int(input())costs = [list(map(int, input().split())) for _ in range(n)]# 최소 비용min_cost = 1..

https://www.acmicpc.net/problem/2468BFS를 사용하여 문제를 풀이하였다.문제 풀이의 포인트는 지도를 저장하며 최대 높이를 구하여 최대 높이 전까지만 물이 차는 경우를 모두 탐색한다.또한, 잠기지 않은 땅인 경우에 해당 영역 기준으로 BFS를 통하여 주변 영역들을 순회하며 잠기지 않은 영역을 구분하고 카운트한다.마지막으로 카운트 된 갯수 중 가장 큰 값을 출력하면 된다.from collections import dequedef bfs(x, y, num): q = deque([(x, y)]) visited[x][y] = True while q: n_x, n_y = q.popleft() # 상하좌우 방향 탐색 fo..

https://www.acmicpc.net/problem/11057dp 테이블을 2차원으로 구성해서 풀어가는 문제규칙만 잘 생각하면 쉬운 문제였다.n = int(input())# 2차원 dp 테이블 생성dp = [[0] * 10 for _ in range(1001)]# 길이가 1인 경우 오르막 수for i in range(10): dp[1][i] = 1 for i in range(2, n + 1): for j in range(10): cnt = 0 # 마지막 자리가 현재 숫자보다 크거나 같은 경우를 모두 카운트 for k in range(j, 10): cnt += dp[i - 1][k] dp[i][j] = cnt ..

https://www.acmicpc.net/problem/11726전형적인 DP 문제로 규칙을 찾아가면 되는 문제n이 1000이하 값으로 크지 않기 때문에 1부터 모두 구해나가면 된다 규칙을 간단히 설명하면,n = 1일때는 아래 그림과 같이 채울 수 있습니다. n = 2일때는 아래 그림과 같이 채울 수 있습니다. n = 3인 경우부터 규칙이 발생합니다. n = 1인 경우 뒤에 1 x 2 블록 두개를 쌓은 경우와 n = 2인 경우 뒤에 2 x 1 블록 한개를 쌓은 경우가 됩니다. 동일한 규칙으로 n = 4인 경우에는 n = 2인 경우 뒤에 1 x 2 블록 두개를 쌓은 경우와 n = 3인 경우 뒤에 2 x 1 블록 한개를 쌓은 경우가 됩니다.  따라서 n = (n - 2) + (n - 1) 의 규칙을 가지게..

https://www.acmicpc.net/problem/1463처음에는 아무 생각 없이 BFS로 풀었다가 시간 초과로 틀린 문제입력이 10의 6승으로 매우 크기 때문에 DP를 이용해 시간 생각을 하면서 풀었어야 했다무작정 풀지말고 생각 먼저 하고 풀기# BFS로 풀어서 시간 초과된 코드from collections import dequen = int(input())q = deque()q.append((n, 0))ans = -1while q: now, times = q.popleft() if now == 1: ans = times break if now % 3 == 0: q.append((now // 3, times + 1)) if now % 2..

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr최단 시간을 구해야 하기 때문에 BFS를 사용해서 풀이하였다.많이 어렵진 않은 문제from collections import deque# 두 단어 사이 다른 글자 개수 확인def check(word1, word2): cnt = 0 for i in range(len(word1)): if word1[i] != word2[i]: cnt += 1 return cn..

https://school.programmers.co.kr/learn/courses/30/lessons/132266 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr처음에는 BFS로 매 source마다 desination까지의 거리를 측정하였다.위의 방식을 사용하면 테스트 케이스 11~15에서 시간초과가 발생하였다.어떻게 해결할지 몰라서 방법을 찾아봤는데 destination을 기준으로 서치를 진행하여 각 위치까지의 거리를 측정하면 되는 문제였다.이마를 탁 치게 된 풀이였다.. 거꾸로 생각해보기# 시간 초과 실패 코드from collections import d..