하나씩 알아가기

토마토가 존재하는 곳으로부터 상하좌우로 하루에 한 칸씩 익어나가는데 며칠이 걸리는 것인지 구하는 문제입니다. 기본적으로 지난번에 풀어본 "미로탐색(BOJ_2178)" 문제와 비슷합니다. 하지만 추가로 생각해야 할 문제가 있었는데 여러 곳에서 토마토가 익어 나갈 수 있다는 점(미로 탐색 문제와 다르게 한 시작점에서 탐색을 해나가지 않는다)입니다. 그래서 토마토 밭에서 1인 곳을 찾아서 큐에다 다 넣어주고 너비탐색을 한 후(미로탐색과 동일하게 1씩 증가시킵니다) 너비탐색이 끝났는데 0인 경우는 -1을 출력하고 얼마나 걸리는 지 구할 때는 단순히 토마토 밭에서 최댓값을 구하면 됩니다. if days < tomatoes[i][j]: days = tomatoes[i][j] 파이썬 삼항 연산자(Ternary ope..

이 문제는 DFS/BFS를 이용한 시뮬레이션 문제입니다. 좌표의 범위 내에서 육지의 지역을 순회하고 이동을 할 수 없으면 카운트를 올려주는 식으로 계산합니다. 말로 하면 간단한데 좌표에서 이동할 수 있는 경우(next position)를 모두 고려해야하므로 좌표의 정보를 구해줘야 합니다. 좌표 시뮬레이션 문제는 늘 그렇듯이 dx와 dy를 더해서 다음 좌표로 이동하기 때문에 dx = [-1,-1,-1,0,0,1,1,1] dy = [-1,0,1,-1,1,-1,0,1] 를 준비합니다. 그리고 이 문제의 경우 다음 지도에서 섬의 개수가 5가 아닌 3인 것을 볼 때 상하좌우 뿐만 아니라 대각선까지 고려해 주어야한다는 것은 알 수 있습니다. 처음에는 DFS를 이용해서 여덟번의 재귀를 하는 식으로 구현했는데... I..

DFS(Depth-First-Search, 깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 동작 과정 ① 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. ② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 ③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. ※ 동작 원리는 스택이지만 구현은 재귀 함수를 이용해서 하는 것이 더 간결합니다. def dfs(graph, v, visited): #현재 노드를 방문처리 visited[v] = True print(v, end=' ') #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in grap..