220512_w4_DFS BFS - Sunny-W-Park/elice-sw2-algorithms GitHub Wiki

박선우 - #2636 치즈

• 문제 보기(출처)
• 풀이 코드

문제 해석

• M, N: 치즈 판의 세로, 가로 길이
• 1시간이 지날 때마다 1로 표시된 구역의 경계가 0으로 바뀜
• 1이 모두 0이 될 때까지 몇시간이 걸리는지, 모두 0이 되기 전에 남아있는 1이 몇개인지 구하기

접근

• BFS 활용
  • 0의 위치 탐색 -> 방문 체크
  • 0 위치에서 상하좌우에 1이 있으면 경계 -> 다시 경계를 방문하지 않도록 방문 체크, 1을 0으로 바꿔주기
• BFS 1회에서 체크한 1의 개수 = 1시간이 지났을 때 0을 1로 바꾼 횟수

풀이 과정

• t: 치즈 판 위에 1의 개수 저장
• BFS 정의
• while문으로 t가 0이 아닐 때까지 bfs반복, bfs 1회 돌때마다
  • 0에서 1로 바꾼 횟수를 t에서 차감해주기(해당 값을 counts 배열에도 저장)
  • 시간 += 1
• time: 총 소요 시간
• counts[-1]: 마지막에 차감한 수

---

백성호 - #13565 침투

• 문제 보기(출처)
• 풀이 코드

문제 해석

• 격자의 크기: M 가로줄의 개수, N 세로줄의 개수
• 전류가 잘 통하는 물질은 0으로 전류가 통하지 않는 물질은 1로 표현된다.
• 밖 (격자의 맨 윗줄)에서 흘려준 전류가 안쪽(격자의 맨 아랫줄)까지 침투 될 수 있는지 구해야 한다.

접근

• DFS 활용: 맨 윗줄에 모든 값에 대하여 0이면 반복적으로 상,하,좌,우로 이동하는 DFS 함수를 활용하여 맨 아랫줄까지 탐색.
• 만약에 DFS 인자의 y값이 맨 아랫줄을 도달했다면, flag를 “NO”에서 “YES”로 변환.
• flag 결과를 출력

풀이 과정

• graph를 0과 1을 원소로 이루어진 2차원 배열로 입력

• DFS 정의

  • x , y를 인자로 받아서, x 나 y가 그래프를 벗어날 index인 경우 return으로 함수를 종료.
  • 만약에 y 인자 값이 m-1이라면, 침투에 성공했다는 뜻이므로 flag를 “YES”로 바꾸고 함수를 종료.
  • 만약에 graph의 x, y 좌표 값이 1이라면 dfs 재귀를 할 수 없으므로 return으로 함수를 종료.
  • graph의 x,y 좌표 값이 0이라면 방문했다는 뜻으로 좌표값을 1로 바꾸고, 상/하/좌/우 dfs 함수 재귀 실행.

• 처음에 flag를 “NO”로 지정해주고, 첫 줄에 모든 원소로 dfs함수를 실행했을 경우 성공 시 flag가 “YES”로 변환되고, 실패 시 “NO”로 유지됨.

• 결과가 담긴 flag를 출력.

지의신 - #2293 토마토

• 문제 보기(출처)
• 풀이 코드

문제 해석

• M, N: 상자 가로 칸의 수, 상자 세로 칸의 수
• 하루가 지날 때마다 0으로 표시된 상자 칸의 값이 1의 값에 인접하다면 1로 바뀜
• 0이 모두 1이 될 때까지 몇일이 걸리는지 구하기, 모두 1이 될 수 없다면 -1

접근

• BFS 활용
  • 큐 사용
  • 1이상의 값인 칸의 위치에서 상하좌우에 0이 있으면 칸의값 더하기 1로 바꿔주기
• 상자 칸중에 제일 큰 값 == 몇일 걸렸는지의 값

풀이 과정

• q: 큐, 처음에 상자에 1의 값들의 위치 인덱스들의 값으로 초기화
• BFS 정의
• while문으로 q가 빌 때까지 bfs반복, bfs 1회 돌때마다
  • 상하좌우에 0의값(아직 방문하지 않은 칸)이 있다면 자기자신 + 1의 값으로 대입
  • 그리고 그 칸의 위치 인덱스 값을 q에 append
• BFS가 끝나고 상자를 순회하여 제일 큰 값을 출력, 만약 상자에 0이(모두 1이 될 수 없다) 하나라도 있다면 -1 출력

---

김재민 - #2606 바이러스

• 문제 보기(출처)
• 풀이 코드

문제 해석

• vertex_cnt, edge_cnt: 컴퓨터 수(노드), 컴퓨터 연결 정보(간선) 수
• 컴퓨터 연결 정보로 컴퓨터 연결 상태 그래프를 그렸을 때 1번 컴퓨터가 바이러스에 걸렸을 경우 피해를 입을 컴퓨터 수 반환

접근

• DFS 활용
  • 1의 위치에서 연결된 컴퓨터를 Stack을 활용하여 방문

풀이 과정

• vertex_list : 입력받은 vertex_cnt를 통해 컴퓨터 번호 생성

• adjacency_list : vertex_list 길이 만큼 2중 list 생성. index 1 list는 1번 컴퓨터의 양방향 연결 상태

• visited_vertex : 방문한 컴퓨터 번호 리스트

• current : 탐색 중 현재 위치

• stack : 현재 위치와 인접한 컴퓨터 리스트 임시 저장

• 현재 문제에서는 1번 컴퓨터와 연결된 노드만 방문

• while문으로 stack이 비어질때까지 반복

  • stack에 저장된 1을 current로 pop
  • for문에서 adjacency_list[1] 의 리스트 요소가 visited_vertex에 없을 경우 (방문하지 않았을 경우) visited_vertex에 append

• for문이 끝나면 cuurent에 있는 나머지 1도 visited_vertex에 append

• visited_vertex를 set으로 중복제거후 1번 컴퓨터를 제외한 숫자 출력

---