개발미정

백준사이트에 있는 시뮬레이션 문제 "치즈" 이다. 골드4의 문제이지만 정답률은 53%로 비교적 쉬운 문제에 속한다! https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 시뮬레이션 연습으로 한 번 풀어보기 좋은 것 같다. 접근 방법 이 문제는 가장자리를 어떻게 찾느냐가 관건이었다. 처음에 접근할 때, 상하좌우에 0이 하나라도 있다면 바로 가장자리라고 생각하고 풀었다. 하지만 그렇게 될 경우, 치즈 속 구멍은 처리하지 못한다. 그래서 다른 방식으로 접근했다. - 입력 데..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 실버 1 난이도 문제이다. 예전에는 어렵게 풀었을텐데, 이젠 가볍게 풀려서 뿌듯했다..ㅎㅎ 더 높은 난이도도 가볍게 풀리는 날이 오기를,,, 문제 요약 NxN 지역 안에 높이가 저장되어 있고, h만큼의 비가 올 경우 높이가 h이하의 지역들은 물에 잠기게 된다. 이 때 안 잠기는 지역의 개수를 안전영역이라고 하는데, 이 안전영역의 개수의 최댓값 구해야 하는 문제. 해결 전략 - bfs 활용하여 해결했다. ..

두 개의 동전이 있고, 보드가 있을 때 두 개의 동전 중 하나만 떨어지면서 그 때의 최소 count를 구하는 문제이다. 문제 접근 BFS로 접근하였고, 다음 3가지만 고려하였다. 1. 두 개의 동전이 모두 안 떨어진 경우 2. 두 개의 동전이 모두 떨어진 경우 3. 한 개의 동전만 떨어진 경우 남 -> 동 -> 북 -> 서 순으로 이동하였고, 1번 경우에는 다음 가고자 하는 위치가 벽인 경우만 고려해주었다. 2번 경우에는 count를 할 필요가 없기 때문에 pass 하였다. 3번인 경우 현재 최소 count와 현재까지의 count를 비교하여서 최소값을 구하였다. 정답 코드 from collections import deque rows, cols = map(int, input().split()) BRD =..

프로그래머스에 DFS/BFS -> 3번째 문제인 "단어 변환" 이다. 주어진 단어들만을 돌면서 begin -> target으로 가는 경로 중 최단 경로의 길이를 구하는 문제이다. 주어진 단어들로만 변경이 가능하고, 한 글자만 다를 경우에만 change가 가능하다. def solution(begin, target, words): answer = 0 min_cnt = 0xffff if target not in words: return 0 def dfs(cur, cnt): nonlocal min_cnt # 최소 cnt보다 현재 cnt가 더 큰 경우, 더 볼 필요가 없어지므로 return if min_cnt < cnt: return # cnt가 words의 길이보다 클 경우 이미 모든 경로를 탐색하게 된 것이므..

프로그래머스의 코딩테스트 연습 -> DFS/BFS 문제 중 마지막 문제인 "여행경로" 이다. "ICN"으로 무조건 시작해서 모든 도시를 지나는 경로들 중 알파벳 순서로 되어있는 경로를 구하면 된다. 먼저, 모든 도시를 지나는 경로들 중 알파벳 순서로 먼저인 경로를 구하기 위해서 tickets 배열을 sort 해주었다. 그래야 for문을 돌 때 순서대로 돌 수 있기 때문이다. def solution(tickets): answer = [] s = ["ICN"] visited = [0] * len(tickets) def dfs(cur, visited, tickets, state): nonlocal answer if len(state) == len(tickets) + 1: answer = state return..

백준 bfs문제인 토마토! 1은 익은 토마토, 0은 익지 않은 토마토, -1은 비어있는 칸을 나타낸다. 4개월 전에 c++로 푼 코드와 오늘 python으로 푼 코드가 조금 다른 것 같아서 비교해보려고 한다. 1. Python코드 from collections import deque def bfs(): visited = [[0 for x in range(N)] for y in range(M)] q = deque() # BRD에서 1인 부분을 먼저 추가하기. # -1인 것의 개수 세기 Mcount = 0 for i in range(M): for j in range(N): if BRD[i][j] == 1: q.append((i,j)) elif BRD[i][j] == -1: Mcount += 1 count =..

bfs를 이용한 기본적인 문제! bfs를 완벽히 이해했다면 쉽게 풀릴문제이다. 8가지의 방향으로 이동하도록 구현하였다. T = int(input()) from collections import deque # q = [] # 방향 dx = [-2, -1, 1, 2, 2, 1, -1, -2] dy = [-1, -2, -2, -1, 1, 2, 2, 1] def bfs(): visited = [[0 for _ in range(N)] for _ in range(N)] visited[stX][stY] = 1 q = deque([(stX,stY)]) while q: newX, newY = q.popleft() if newX == enX and newY == enY: return visited[newX][newY] f..