2023년 8월 9일 알고리즘 문제풀이
문제 1 백준 11725
1차 시도
나의 생각
연결된 두 점 중 누구를 부모로 할 것인가에 대해 많이 고민했다. 확실한 것은, 1번과 연결된 노드들의 부모는 모두 1번 노드일 것이라는 것이다. 그래서 모두 1번노드 쪽으로 향하니 번호가 작은 노드가 부모인 것으로 설정해야하나 고민했다. 물론 나도 지금 생각해보면 뭔 말도 안되는 소리인지 모르겠다. 결국 어떤 방법으로 풀어야 할지 감을 못잡았다
결과
오답
코드
X
2차 시도
나의 생각
지금 내가 공부하고 있는 단원이 DFS인 것을 떠올리니 쉽게 해결됐다. 실제 코딩 테스트에선 단원을 모로는 채로 풀어야 하기 때문에 문제만 보고 알아차려야 하는데.. 걱정이다
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
a,b = map(int,sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
ans = [0 for _ in range(n+1)]
def dfs(x):
for i in graph[x]:
if not ans[i]:
ans[i] = x
dfs(i)
dfs(1)
for i in range(2,n+1):
print(ans[i])
문제 2 백준 1707
1차 시도
나의 생각
간선으로 연결된 노드들을 인접해 있다고 하는데, 인접한 노드가 같은 집합에 속해있지 않은 것이 이분 그래프이다. 더 쉽게 말하자면, 어떤 노드를 빨간색으로 칠하고 간선으로 연결된 노드를 파란색으로 칠하면서 계속 진행할때, 간선으로 연결된 노드가 같은 색깔로 칠해져있다면 이 그래프는 이분 그래프가 아닌 것이다. 따라서 아직 방문하지 않는 노드는 0 으로 두고 빨간색과 파란색을 각각 1과 2로 설정하여 인접한 노드들이 이미 칠해졌는지, 칠해졌다면 같은 색인지를 따졌다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys
sys.setrecursionlimit(10**6)
k = int(sys.stdin.readline())
def dfs(x):
global ans
tmp = visited[x]
for i in graph[x]:
if not visited[i]:
if tmp == 1:
visited[i] = 2
else:
visited[i] = 1
dfs(i)
else:
if visited[i] == tmp:
ans = 'NO'
return
for _ in range(k):
ans = 'YES'
v,e = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(v+1)]
for _ in range(e):
a,b = map(int,sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
visited = [0 for _ in range(v+1)]
for i in range(1, v+1):
if not visited[i]:
visited[i] = 1
dfs(i)
if ans == 'NO':
break
print(ans)
문제 3 백준 21606
1차 시도
나의 생각
실내를 시작점으로 설정한 후, dfs로 모든 경로를 탐색하면서 실내를 만날때는 산책로과 완성되었으므로 cnt를 +1 해주고, 실외를 만나면 dfs를 통해 다음 지점을 탐색하도록 구현하였다. 하지만 알고리즘이 작동하지 않았다. 로직에 문제는 없는것 같은데..
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
arr = list(sys.stdin.readline().rstrip())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
u,v= map(int,sys.stdin.readline().split())
graph[u].append(v)
graph[v].append(u)
visited = [False for _ in range(v+1)]
cnt = 0
def dfs(x):
global cnt
for i in graph[x]:
if not visited[i]:
visited[i] = True
if arr[i-1] == 1:
cnt += 1
else:
dfs(i)
for s in range(n):
if arr[s-1]:
visited[s] = True
dfs(s)
print(cnt)
2차 시도
나의생각
위 코드가 잘못된 이유를 찾았다. 배열 arr에는 문자열이 저장되어있다. 비록 1과 0이라도.. 그래서 arr의 원소에 관한 조건문에서 비교를 1,0 이라는 정수값으로 하면 안되고 ‘1,’0’ 으로 했어야 했다. 그렇게 하니 38점이 나왔다. 이젠 로직의 문제..
결과
38/200점
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
arr = list(sys.stdin.readline().rstrip())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
u, v = map(int, sys.stdin.readline().split())
graph[u].append(v)
graph[v].append(u)
visited = [False for _ in range(v+1)]
cnt = 0
def dfs(x):
global cnt
for i in graph[x]:
if not visited[i]:
if arr[i-1] == '1':
cnt += 1
else:
visited[i] = True
dfs(i)
visited[i] = False
for s in range(1, n+1):
if arr[s-1] == '1':
visited[s] = True
dfs(s)
visited[s] = False
print(cnt)
3차 시도
나의 생각
백준에서 다른 사람의 답안을 보고 이해했다. 핵심 논리를 우선 설명하겠다.
산책로의 조건은
- 출발지와 도착지가 모두 실내일것
- 중간 경로는 모두 실외일 것
두 가지이다. 조건에 부합하는 완성된 산책로는 2가지로 구분하면 실외를 거치는 것과 안거치는 것이다.
실외를 안 거치는 것은 말 그대로 산책로가 실내에서 시작하여 바로 인접한 실내로 도착하는 경우를 의미한다. 실외를 거치는 것은? 실내 - (실외) - 실내 로 구성되는 산책로이다. 여기서 중요한 점은 중간 경로에 있는 실외 경로의 갯수는 무의미하다는 것이다. 문제의 2번째 문단 마지막 문장에 다음과 같이 써있다.
트리 위의 두 점 사이의 경로는 유일하므로 시작점과 도착점이 정해지면 경로는 유일하게 결정됩니다.
즉 1번 장소에서 10번 장소 까지 갈 떄 그 사이에 몇군데를 들리는 지는 생각할 필요가 없다! 따라서 dfs로 탐색을 하다
- 지금 도착한 장소가 실내면? : “산책로 하나를 발견했군”
- 지금 도착한 장소가 실외면? : “실내를 찾아 더 깊이 가봐야겠군”
둘을 설정하면 되는 문제이다.
이제 순차적으로 코드의 로직에 대해 말하겠다.
노드간의 연결을 표시하는 배열(graph),체크를 위한 배열(visited)과, 실내외 여부를 표시할 배열(arr)을 만든다. arr배열은 index는 0부터 시작하기 때문에 항상 확인할 때 1을 빼야 한다.
dfs를 정의한다. 출발점과 visited,graph,arr을 parameter로 받는다. 출발점 x에서 간선이 연결된 후보를 i로 설정하고 후보들을 순회한다. 그 i가 실내라면 출발과 도착이 모두 실내인 산책로가 완성되었으므로 cnt에 1을 더해준다. 실외라면 더 진행해야하므로 방문 표시를 한 후 재귀에 돌입한다. 결국 이 함수는 cnt를 반환하도록 구현한다. 즉 재귀함수 dfs는 도착지가 실내일 때만 cnt를 1 더하도록 구현되어 있기 때문에 parameter로 받은 출발지에서 실내로 도착하는 산책로의 갯수를 반환하는 함수이다. 바꿔 말하면
출발지로 설정한 노드에서 실내 장소를 통하지 않고 갈 수 있는 실내 장소의 갯수
라는 뜻이기도 하다. 즉 출발지 - 실내 , 출발지 - 실외 - 실외 - 실내 등등을 모두 포함하고 있지만, 반면 실외 - 실내 - 실내와 같은 경우는 포함하지 않는다. 실내를 만나는 순간 함수는 재귀에 돌입하지 않으니까!
따라서 모든 장소를 순회하면서 출발지로 설정한다. 출발지가 실내면? 함수를 통해 도착지가 실내인 경우를 찾아 세주면 된다.
출발지가 실외면? 함수를 통해 도착지가 실내인 경우의 갯수를 세주면 된다. 그리고 1을 뺸 값을 곱하면 된다. 산책로를 중간 경유지인 실외의 입장에서 보면 실외에서 갈 수 있는 실내의 갯수는 위에서 말했듯 재귀함수를 통해 구할 수 있다. 갈 수 있는 실내의 갯수는 다시 말해 이 실외 장소를 경유하는 산책로에서 출발지로 설정할 수 있는 실내의 갯수라는 의미이다. 도착지는? 출발지로 설정한 장소 1개를 뺀 나머지 모든 실내가 후보지이다. 그래서 1을 뺸값을 곱해주는 것이다.
내가 써놓고도 너무 어려워서 한번 더 정리해보겠다..
- 산책로는 두 경우로 나눈다. 실내-실내 다이렉트로 이어진 경우와 중간에 실외가 끼인 경우.
- 실외가 끼인 경우 끼인 실외가 몇개인지는 무의미하다. 1개든, 100개든 1개로 생각해도 된다.
- 그렇다면 실외 장소 하나를 기준으로 연결된 실내의 갯수는 재귀함수를 통해 구할 수 있다.
- 실외 장소 하나를 기준으로 재귀함수를 통해 구한 숫자를 k 라고 해보자.
- 이 실외 장소를 경유하는 산책로를 위해서 설정할 수 있는 출발지의 후보는? k개이다.
- 도착지는? 출발지로 설정한 것 1개를 뺸 k-1 개이다.
- 출발지 k개, 도착지 k-1개 를 곱해서 k(k-1)이 나오는 것.
결과
이해
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys
sys.setrecursionlimit(10**6)
def dfs(x,visited,graph,arr):
cnt = 0
for i in graph[x]:
if arr[i-1] == '1':
cnt += 1
else:
if not visited[i]:
visited[i] = True
cnt += dfs(i,visited,graph,arr)
return cnt
n = int(sys.stdin.readline())
arr = list(sys.stdin.readline().rstrip())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
visited[0] = True
for _ in range(n-1):
u,v = map(int,sys.stdin.readline().split())
graph[u].append(v)
graph[v].append(u)
ans = 0
for i in range(1,n+1):
if arr[i-1] == '0':
if not visited[i]:
visited[i] = True
tmp = dfs(i, visited, graph, arr)
ans += tmp*(tmp-1)
else:
for j in graph[i]:
if arr[j-1] == '1':
ans += 1
print(ans)
