JUNGLE 240403 (W02)

in Study #Jungle

KRAFTON JUNGLE Week 02

1. BOJ Issue

21606. 아침 산책

  1. 실외 노드를 1개 거치는 경우
    • 실내 -> 실외 -> 실내의 경로를 가지므로 본인을 제외한 다른 실내 노드로 가는 경로를 세면 된다.
    • 즉, 주변 실내 노드의 개수를 in_cnt라 했을 때 in_cnt * (in_cnt - 1)
      if place[i] == 0 and not visited[i]:                           # 실외 노드를 기준으로
 in_cnt = dfs(i)                                             # 주변 실내 노드 계산
 answer += in_cnt * (in_cnt - 1)                             # 경우의 수 추가
  2. 실외 노드를 2개 이상 거치는 경우
    • 실외 노드가 2개 이상 연결되어 있어도 시작점과 목적지가 실내 노드라는 점은 같음
    • 인접한 노드가 실외 노드라면 그 노드를 타고 가서 그 실외 노드의 주변 실내 노드를 세면 된다.
            # dfs() 함수 내에 경우의 수 추가
      elif not visited[neighbor] and place[neighbor] == 0:        # 방문한 적 없고 해당 위치가 실외라면,
          inside += dfs(neighbor)                                 # 해당 실외 노드에서 dfs
  3. 실외 노드끼리 떨어져 있는 경우
    • 실외 노드끼리 떨어져 있다면, 다른 경우의 수로 쪼개버린 다음 경로의 수를 각각 구해주면 된다.
    • 1번 코드를 통해 경우의 수는 각각 추가됨
  4. 실외 노드를 거치지 않는 경우
    • 실내 <-> 실내, 즉 양방향의 경우가 가능하므로 경우의 수를 +2 해준다.
        if place[a] == 1 and place[b] == 1:                             # 둘 다 실내라면
      answer += 2                                                 # 서로 방문하는 경우 추가 (+2)
전체 코드
N = int(input())
A = input().rstrip()
graph = [[] for _ in range(N+1)]
place = [0] + [int(x) for x in A]                                   # 실내인지 실외인지 입력 받음
visited = [False] * (N+1)
answer = 0

for _ in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

    if place[a] == 1 and place[b] == 1:                             # 둘 다 실내라면
        answer += 2                                                 # 서로 방문하는 경우 추가 (+2)


def dfs(node):                                                      # 정점 번호
    visited[node] = True                                            # 방문 처리
    inside = 0                                                      # 실내 개수 카운트
    for neighbor in graph[node]:                                    # 이웃 노드에 대해서
        if place[neighbor] == 1:                                    # 이웃 노드가 실내라면
            inside += 1                                             # 실내 개수 +1
        elif not visited[neighbor] and place[neighbor] == 0:        # 방문한 적 없고 해당 위치가 실외라면,
            inside += dfs(neighbor)                                 # 해당 실외 노드에서 dfs
    return inside

for i in range(1, N+1):
    if place[i] == 0 and not visited[i]:                            # 실외 노드를 기준으로
        in_cnt = dfs(i)                                             # 주변 실내 노드 계산
        answer += in_cnt * (in_cnt - 1)                             # 경우의 수 추가

print(answer)

1707. 이분 그래프

def dfs(graph, start, visited, index):
    if visited[start] != 0:                 # 현재 노드가 이미 방문되었는지 확인
        return visited[start] == index      # 이미 할당된 색과 현재 색이 같은지를 확인하여 이분 그래프 여부 판별

    visited[start] = index                                      # 현재 노드에 색 할당
    for neighbor in graph[start]:                               # 현재 노드와 인접한 이웃 노드에 대해
        if visited[neighbor] == 0:                              # 만약 방문한 적이 없다면
            if not dfs(graph, neighbor, visited, -index):       # 함수 재귀 호출 (현재 노드와 다른 색을 할당하여 호출)
                return False
        elif visited[neighbor] == visited[start]:               # 인접한 노드가 이미 방문되었고, 색이 현재 노드와 같다면
            return False                                        # False 반환
    return True                                                 # 위의 조건을 모두 통과하면, True 반환
  • dfs 탐색을 하면서 각각의 노드에 색을 할당
  • 이웃 노드와 색이 같은지 확인하여 이분 그래프 판별