juyeonma · Sep 27, 2023 · Sep 15, 2023
diff --git a/.gitignore b/.gitignore
@@ -10,6 +10,7 @@
 백준_15665_N과-N-11.py
 백준_15666_N과-N-12.py
 백준_11054_가장-긴-바이토닉-부분-수열.py
+프로그래머스_43162_네트워크.py
 #########
 
 # Byte-compiled / optimized / DLL files

diff --git a/Programmers/Programmers_Lv2/README.md b/Programmers/Programmers_Lv2/README.md
@@ -46,4 +46,4 @@
 |150368_이모티콘 할인행사|Lv. 2|❌|[프로그래머스](https://school.programmers.co.kr/learn/courses/30/lessons/150368)|
 |42860_조이스틱|Lv. 2|❌|[프로그래머스](https://school.programmers.co.kr/learn/courses/30/lessons/42860)|
 |42584_주식가격|Lv. 2|❌|[프로그래머스](https://school.programmers.co.kr/learn/courses/30/lessons/42584)|
-
+|43162_네트워크|Lv. 2|✔|[프로그래머스](https://school.programmers.co.kr/learn/courses/30/lessons/43162)|
diff --git a/graph_traversal/README.md b/graph_traversal/README.md
@@ -37,6 +37,7 @@
 |문제명|난이도|성공|문제|
 |-----|:----:|:----:|:----:|
 |16918_봄버맨|실버 1|✔|[백준](https://www.acmicpc.net/problem/16918)|
+|11403_경로-찾기|실버 1|❌|[백준](https://www.acmicpc.net/problem/11403)|
 |16234_인구 이동(이코테_21)|골드 5|✔|[백준](https://www.acmicpc.net/problem/16234)|
 |22856_트리 순회|골드 4|❌|[백준](https://www.acmicpc.net/problem/22856)|
 |14502_연구소(이코테_16)|골드 4|❌|[백준](https://www.acmicpc.net/problem/14502)|
@@ -46,5 +47,6 @@
 |5427_불|골드 4|❌|[백준](https://www.acmicpc.net/problem/5427)|
 |2573_빙산|골드 4|❌|[백준](https://www.acmicpc.net/problem/2573)|
 |16973_직사각형 탈출|골드 4|✔|[백준](https://www.acmicpc.net/problem/16973)|
+|12851_숨바꼭질2|골드 4|❌|[백준](https://www.acmicpc.net/problem/12851)|
 |2206_벽 부수고 이동하기|골드 3|❌|[백준](https://www.acmicpc.net/problem/2206)|
 |9466_텀 프로젝트|골드 3|❌|[백준](https://www.acmicpc.net/problem/9466)|
diff --git a/graph_traversal/백준_11403_경로-찾기.py b/graph_traversal/백준_11403_경로-찾기.py
@@ -0,0 +1,38 @@
+'''
+# 백준_11403_경로-찾기. 실버 1. 풀이: 23.09.15 -> 실패
+
+# How to
+
+## 반례
+
+# Review
+- 풀이 시간:
+- 구상하는게 어려웠다. 실버 1인데도..
+- 간신히 DFS로 했지만, 시간초과. BFS로 해야하는걸까?
+'''
+
+# Code
+# 1. DFS: 시간초과 실패
+## 메모리:  KB, 시간:  ms
+import sys
+input = sys.stdin.readline
+
+n = int(input())
+arr = [list(map(int, input().split())) for _ in range(n)]
+
+def dfs(i, road):
+    for j in range(n):
+        # 연결된다면
+        if arr[i][j]:
+            # 이전 경로와도 연결하고
+            for before in road:
+                arr[before][j] = 1
+            # 경로에 추가하며 dfs 재귀로 들어간다.
+            if i not in road:
+                dfs(j, road|{i})
+
+for i in range(n):
+    dfs(i, set())
+
+for i in arr:
+    print(*i)
diff --git a/graph_traversal/백준_12851_숨바꼭질2.py b/graph_traversal/백준_12851_숨바꼭질2.py
@@ -0,0 +1,58 @@
+'''
+# 백준_12851_숨바꼭질2. 골드 4. 풀이: 23.09.15 -> 실패
+
+# How to
+- BFS
+- 걷거나 or 순간이동 하면서
+    - 더 낮은 시간이면, 시간 갱신 및 큐에 추가
+    - 이미 최저 시간이면, 경우의 수 +1
+
+## 예제
+5 17
+10 9 18 17 => 4초
+10 20 19 18 17 => 4초
+
+## 반례
+5 237
+답: 
+10
+5
+
+# Review
+- 풀이 시간: 2시간..
+- 반례찾느라 시간 다보냈다. 결국 질문게시판을 봤는데, 역시 반례에서 틀렸더라.
+- 도저히 왜 틀렸는지 모르겠다 ㅠㅠ
+    - 방문처리 및 정답 기록을 딕셔너리로 했는데, 이게 아닌가..?
+    - 숨바꼭질3는 맞았는데 숨바꼭질2는 틀린걸 보면, 경우의 수를 세는게 문제같다.
+'''
+
+# Code
+# 1. BFS: 40%에서 실패
+## 메모리:  KB, 시간:  ms
+from collections import deque
+n, k = map(int, input().split())
+
+# 수빈이의 위치별 시간과 경우의 수 딕셔너리
+subin = {n: [0, 1]}
+
+def bfs(x):
+    q = deque([x])
+    while q:
+        x = q.popleft()
+        if x == k:
+            continue
+
+        # 걷거나 순간이동 하면서
+        for nx in [x+1, x-1, 2*x]:
+            if 0 <= nx <= 100_000:
+                # 새로운 위치이거나 더 낮은 시간이면, 시간 갱신 및 큐에 추가
+                if nx not in subin or subin[x][0]+1 < subin[nx][0]:
+                    subin[nx] = [subin[x][0]+1, subin[x][1]]
+                    q.append(nx)
+
+                # 이미 최저 시간이면, 경우의 수 +1
+                elif subin[x][0]+1 == subin[nx][0]:
+                    subin[nx][1] += 1
+
+bfs(n)
+print(subin[k], sep='\n')
diff --git a/graph_traversal/백준_13549_숨바꼭질3.py b/graph_traversal/백준_13549_숨바꼭질3.py
@@ -0,0 +1,45 @@
+'''
+# 백준_13549_숨바꼭질3. 골드 5. 풀이: 23.09.15
+
+# How to
+- BFS
+- 걷거나 or 순간이동 하면서
+    - 소요 시간 갱신, 큐에 추가(타겟으로 계속 이동)
+
+## 예제
+5 17
+10 9 18 17 => 2초
+10 20 19 18 17 => 3초
+
+# Review
+- 풀이 시간: 숨바꼭질2 풀고 바로. 10분?
+- 실수로 숨바꼭질2를 먼저 풀고나서 숨바꼭질3를 풀었는데, 거의 유사해서 바로 풀었다.
+- 다만 시간이 빠르진 않는데, 맞힌 사람을 보니까 k < n인 경우는 순간이동을 못한다는 조건을 추가해야했다.
+'''
+
+# Code
+# 1. BFS: 성공
+## 메모리: 46160 KB, 시간: 140 ms
+from collections import deque
+n, k = map(int, input().split())
+
+# 수빈이의 위치별 소요시간과 경우의 수 딕셔너리
+subin = {n: 0}
+
+def bfs(x, target):
+    q = deque([x])
+    while q:
+        x = q.popleft()
+        if x == target:
+            return subin[x]
+
+        # 걷거나 순간이동 하면서
+        for nx, a in [(x+1, 1), (x-1, 1), (2*x, 0)]:
+            if 0 <= nx <= 100_000:
+                # nx가 처음이거나 더 낮은 소요 시간이면,
+                # 소요 시간 갱신, 큐에 추가
+                if nx not in subin or subin[x]+a < subin[nx]:
+                    subin[nx] = subin[x] + a
+                    q.append(nx)
+
+print(bfs(n, k))
diff --git a/graph_traversal/백준_1743_음식물-피하기.py b/graph_traversal/백준_1743_음식물-피하기.py
@@ -0,0 +1,51 @@
+'''
+# 백준_1743_음식물-피하기. 실버 1. 풀이: 23.09.15
+
+# How to
+- 쓰레기의 위치를 통로(board)와 쓰레기 모음(trash)에 추가
+- BFS로 각각의 쓰레기마다 덩어리 크기를 재고, 정답을 갱신
+    - 연결된 쓰레기를 큐에 넣을 때마다 쓰레기를 치워야(즉 0으로 바꿔줘야) 중복 방지됨
+
+# Review
+- 풀이 시간: 20분
+'''
+
+# Code
+# 1. BFS
+## 메모리: 34176 KB, 시간: 80 ms 
+from collections import deque
+import sys
+input = sys.stdin.readline
+
+n, m, k = map(int, input().split())
+# board: 통로 배열, trash: 쓰레기 위치만 모아놓음
+board = [[0]*m for _ in range(n)]
+trash = []
+
+for _ in range(k):
+    r, c = map(int, input().split())
+    board[r-1][c-1] = 1
+    trash.append((r-1, c-1))
+
+def bfs(i, j):
+    q = deque([(i, j)])
+    board[i][j] = 0
+    cnt = 0
+    while q:
+        x, y = q.popleft()
+        cnt += 1
+        for i, j in zip([1,-1,0,0], [0,0,1,-1]):
+            nx, ny = x+i, y+j
+            # 범위 안이고, 쓰레기일 경우, 큐에 추가 후 쓰레기 치움(중복 방지)
+            if 0 <= nx < n and 0 <= ny < m and board[nx][ny]:
+                q.append((nx, ny))
+                board[nx][ny] = 0
+
+    return cnt
+
+# 각각의 쓰레기마다 덩어리 크기를 측정하고 정답 갱신
+answer = 0
+for i, j in trash:
+    answer = max(answer, bfs(i, j))
+
+print(answer)