내 맴

문제 ) https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net [ 풀이 IDEA ] 1. BFS/DFS로 풀어야하는 문제! 2. 그러나, 단순히 풀면 시간에러가 난다. 💡 SET 이용해서 문제 해결! ▶ BFS의 경우, queue대신에 set을 사용 & set에 좌표/visited(지나온 알파벳)을 저장한다 - python code dx = [0,0,-1,1] dy = [-1,1,0,0] def solution(board): global ma..

문제 ) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net [ 풀이 ] 아파트들을 모두 순회해야함으로 탐색 알고리즘 DFS를 사용하여 문제를 풀어보았다. 우선, 입력받은 값들 (집의 위치)을 home list에 저장하였고 방문한 집을 표시하는 visit list도 만들어주었다. 또한, 방향을 알려주는 list인 dx와 dy를 이용하여 문제를 풀어주었다. 현재 집을 기준으로 오른쪽,왼쪽,위,아래에 있는 집들을 접근하기 위한 list이다. x좌표 (..

문제 ) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net [ 풀이 ] 그래프 탐색에 대한 문제이다. BFS, DFS 방법으로 둘 다 구현해 보았다. 먼저, DFS방법으로 푼 코드이다. 재귀함수를 이용해준다. - Python code (DFS ) visit=[1] def DFSWorm(current): global count, visit for i in range(1,n+1): # 바이러스에 걸리지 X & 길이 연결되어있는 경우 if i not i..

문제 ) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [ 풀이 ] BFS 와 DFS에 대한 문제이다. DFS와 BFS는 이진트리로 밖에 안해봤었는데 이 문제는 조금 달랐다 . DFS의 경우 , 만약 Node사이에 연결선이 존재한다면 연결된 Node부터 이어주게 된다. 그러나 BFS의 경우에는 level이 같은 Node들 부터 출력하게 된다. - DFS 설명 https://luz0911.tistory.co..

- DFS ( Depth First Search ) : Root Node 방문 후, 그 Node의 후손들을 왼쪽에서 오른쪽으로 Search - 구현 방법 1. GRAPH 표현해주기 ( python ) : Dictionary 과 List 자료형을 사용해준다 1개의 Node와 연결되어있는 Node들을 모두 다 표현해준다 2. DFS 구현하기 ( python ) : Stack를 이용하여 구현한다. - 전체 code