하나씩 알아가기

토마토가 존재하는 곳으로부터 상하좌우로 하루에 한 칸씩 익어나가는데 며칠이 걸리는 것인지 구하는 문제입니다. 기본적으로 지난번에 풀어본 "미로탐색(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..

틀린 부분이 있을 경우, 지적해 주시면 감사하겠습니다. 노드, 간선, 시작점을 첫째 줄에 입력 받고 둘째 줄 부터는 간선의 개수만큼 두 정점의 번호를 입력 받습니다. 두 개의 리스트를 생성합니다. 연결 정보를 나타낸 2차원 리스트 방문 여부를 기록한 1차원 리스트 이 정점을 연결 정보를 인접 행렬(adjacent matrix)로 다음과 같이 나타낼 수 있습니다. 0 1 2 3 4 1 1 1 1 2 1 1 3 1 1 4 1 1 연결이 되어 있다면 1을 넣어주었습니다. 가장 핵심이 되는 부분은 방문하지 않은 노드면서 연결이 되어있는 노드를 방문해 나가는 것인데 dfs의 경우 재귀함수를 호출하고 bfs일 때는 큐에다가 넣어줍니다 from collections import deque n, m, v = map(i..

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