3주차 (07월 18일)
목표
- 알고리즘 < BFS / DFS > 문제풀기 (백준 2606번, 백준 2667번, 백준 1697번)
회고
- 알고리즘 < BFS / DFS > 문제 : 백준 2606번(“바이러스”) -> 난이도 : 실버3
해결 방법 : 서로 이어진 컴퓨터들을 graph로 저장을 한 후에 dfs를 통해서 연결된 모든 컴퓨터를 찾으면서 컴퓨터의 수를 1씩 증가한다.
코드일부
def dfs(node):
global count
if not check[node]:
check[node] = True
count += 1
for k in graph[node]:
dfs(k)
return
for _ in range(c):
i, j = map(int, input().split())
graph[i].append(j)
graph[j].append(i)
dfs(1)
print(count - 1)
- 알고리즘 < BFS / DFS > 문제 : 백준 2667번(“단지번호붙이기”) -> 난이도 : 실버1
해결 방법 : 2차원 리스트에 아파트의 위치를 저장한 후에 dfs를 통해서 연결된 집을 찾고, dfs를 할 때마다 집의 수를 카운트한다.
코드일부
def dfs(a, b):
global count
if not check[a][b] and int(home[a][b]) == 1:
check[a][b] = True
count += 1
for k in range(4):
newx = a + dx[k]
newy = b + dy[k]
if 0 <= newx < N and 0 <= newy < N:
dfs(newx, newy)
return
for i in range(N):
for j in range(N):
if int(home[i][j]) == 1 and not check[i][j]:
totalCount += 1
dfs(i, j)
countList.append(count)
count = 0
countList.sort()
print(totalCount)
for i in countList:
print(i)
- 알고리즘 < BFS / DFS > 문제 : 백준 1697번(“숨바꼭질”) -> 난이도 : 실버1
해결 방법 : BFS를 통해서 해결해야하는 문제인데 현재 위치에 접근하면 +1, -1 *2의 위치를 접근하고 큐에 넣는다. 새로 접근하는 위치는 전 위치의 +1 값을 저장해서 시간을 카운트 해준다.
답이 나오는데 백준에서는 틀렸다고 나와서 다음 모각코 전까지 맞춰서 와야겠다.