링크 https://www.acmicpc.net/problem/7576 난이도(solved.ac 참고) 실버1 풀이 음 .. IndexError가 계속 떠서 무엇이 문제인가 했는데, 위 코드는 정답 코드지만 내가 계속 제출했다가 틀린 코드는 마지막 행에서 bfs(m, n)이 아니라 bfs(queue[0][0], queue[0][1])로 넣었었다. 이렇게 되면 상자 내에 토마토가 없을 때, 즉 리스트의 값이 전부 -1 또는 0만 있을 때 -1을 출력할 수 없고 IndexError가 뜨게 된다. 풀이 과정 함수 바깥에서 일단 이중 for문으로 input값을 받아서 만든 리스트(a) 내에 1이 있으면 큐에 그 좌표를 넣는다. 큐가 있다는 건 결국 1로 바뀐 무엇인가가 존재한다는 뜻이므로, while queue..

링크 https://www.acmicpc.net/problem/1260 난이도(solved.ac 참고) 실버2 풀이 걍 뭐.. 설명할 것도 없다. 이거 못풀면 다른 모든 그래프 탐색 문제도 못 푼다.. 일반적인 DFS와 BFS 구현에서 아주 살짝 달랐던 점은, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점이다. 이 부분은, v 지점을 방문 표시한 뒤에 인접 리스트의 인덱스 v를 기준으로 연결된 여러 정점 중 가장 작은 것부터 방문해야 된다는 뜻이다. 따라서, graph에 대한 for문을 돌 때 sorted() 처리를 해주면 된다. 아 그리고, 인접 리스트의 총 길이는 n과 m 중 큰 값 + 1만큼 되어야 한다는 점도 고려해야 한다. 예를 들어 정점은 1000개지만 ..

자료구조 - 그래프 탐색 그래프 탐색이란? 하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것. 이런 무방향 그래프가 있다고 해보자. B 노드에서 탐색을 시작한다고 할 경우, 결국 모든 데이터를 돌게 된다. 그래프 같은 경우에도 연결된 모든 데이터를 순회하므로 그래프 순회라고도 부른다. 그래프 순회를 통해 알 수 있는 것은, A - BCD 이런식으로 A만 빼고 B ~ D가 연결이 되어 있는 그래프의 경우 A와 B, C, D는 서로 연결되지 않았다는 사실이다. 탐색을 사용하는 또다른 대표적인 예시는 그래프에서 두 노드 사이 최단 경로를 구하는 방법이다. 그래프 순회를 통해 A와 D 사이에 몇 다리가 걸쳐 있는지를 알 수 있게 된다. 그래프 탐색 알고리즘은, 각 노드를 어떤 순서로 탐색하는지에 따라 BFS..