99클럽 TIL (240821)

> [Middler] 점프 점프

https://www.acmicpc.net/problem/14248

 

문제 풀이 과정

오랜만에 백준이라 입력 방법에서 런타임에러(Valueerror)가 발생했다. 이유는 input().split(" ")라고 사용해서인 것 같다. 

 

* '공백' 구분자 기준 문자열 나누기

• python : 문자열.split()
• javascript : 문자열.split(" ") or 문자열.split(/\s+/g)

 

[동작 과정]

1. 입력값들을 input()으로 받는다.

2. 돌개수 n만큼 visited 배열을 초기화한다.

3. stack에 시작점 s를 넣고 해당 start 인덱스에서 start + arr[start], start - arr[start] 한 위치를 확인한다.

4. 이동한 위치가 방문하지 않았다면 방문처리하고 방문 가능한 돌의 개수를 +1하고 큐에 넣는다.

 

위의 과정을 거쳐 문제를 처음 풀었더니 틀렸다...? 코드를 살펴보니 왼쪽, 오른쪽으로 모두 살펴주는 로직 부분을 이상하게 작성했더라... 왜 그렇게 작성했을까..? 잠깐 멍때렸나보다 그래서 다시 알맞게 코드를 바꿔주었다.

 

문제 풀이

python

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
visited = [False] * n
s = int(input())

res = 1
stack = [s-1]
while stack :
    start = stack.pop()
    visited[start] = True
    
    for nx in (start + arr[start], start - arr[start]) :
        if 0 <= nx < n and not visited[nx] :
            res+=1
            stack.append(nx)

print(res)

 

시간복잡도 O(N)

 

회고 및 느낀점

DFS는 스택, BFS 큐

---

> [Beginner]  Clear Cold Water

https://www.acmicpc.net/problem/6188

 

 

문제 풀이 과정

헛간으로 부터 모든 분기점까지의 거리를 구하는 문제. 

 

[동작 과정]

1. 분기점, 분기점으로부터 연결된 다른 분기점들의 정보를 입력받아 연결리스트 생성

2. 거리테이블(d) 초기화한다. 1번 분기점의 거리를 1로 초기화한다.

3. bfs를 1번 분기점부터 시작한다.

4. 연결된 다른 분기점을 돌면서 d[nx] == 0 이면 d[x] + 1해준다. bfs(nx)로 돌린다.

 

문제 풀이

python

import sys
input = sys.stdin.readline

N, C = list(map(int, input().split()))
arr = [[] for _ in range(N+1)]
d = [0 for _ in range(N+1)]
# 연결리스트 만든다.
for i in range(C) :
    e, b1, b2 = list(map(int, input().split()))
    arr[e].append(b1)
    arr[e].append(b2)
    arr[b1].append(e)
    arr[b2].append(e)

# dfs 돌면서 현재 노드의 거리는 이전거리 + 1해준다.
d[1] = 1
def bfs(start) :
    for nx in arr[start] :
        if d[nx] == 0 :
            d[nx] = d[start] + 1
            bfs(nx)
bfs(1)
for x in range(1, len(d)) :
    print(d[x])

 

시간복잡도 O(N)

 

회고 및 느낀점

^_____^ 영어공부 필수.

---

> [Challenger] 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162#

 

 

문제 풀이 과정

정점, 간선 으로 이루어진 그래프를 탐색하여 풀 수 있는 문제로 DFS/BFS로 풀 수 있다. 나는 BFS로 풀었다.

주어지는 computers가 행렬로 이루어져 있는데 문제 설명에도 나와있듯이 [i][j] == 1이면 서로 연결되어 있다. i==j 이면 무조건 1이다 자기자신 이기 때문.

연결행렬로 풀어도 되겠다는 생각은 나중에 들었다. 그래서 우선 익숙한 연결 리스트를 만들었다.

 

[동작 과정]

1. computers를 이중 순회하며 연결 리스트를 만든다.

2. 노드 개수만큼 방문 테이블 초기화, 시작 노드의 방문 테이블 방문처리, 간선의 개수(edge) 초기화

3. 시작노드를 큐에 넣고 큐를 꺼내 큐의 연결 노드들을 확인한다. 

4. 방문한적이 없다면 방문처리, edge + 1 후 큐에 넣는다.

5. 큐에 요소가 없을 때까지 반복

import heapq
def solution(n, computers):
    arr = [[] for _ in range(n+1)]
    nodes = [0 for _ in range(n+1)]
    
    for i in range(len(computers)) :
        for j in range(len(computers[i])) :
            if i != j and computers[i][j] == 1 :
                arr[i+1].append(j+1)
    
    def bfs(start) :
        nodes[start] = 1
        edge = 0
        q = []
        heapq.heappush(q,start)
        
        while q :
            front = heapq.heappop(q)
            for nx in arr[front] :
                if nodes[nx] != 1 :
                    nodes[nx] = 1
                    edge += 1
                    heapq.heappush(q, nx)
        return edge
                
    return n - bfs(1)

 

결과는 틀림!

 

흠 고민하다가 질문하기 탭을 살펴봤는데, 힌트를 얻을 수 있었다. 문제를 다시 읽어보면 어디에도 시작하는 노드가 1번 노드라고 말해준 적이 없다...! 뚜둥 그렇기 때문에 위처럼 코드가 돌때는 1번 노드에 연결된 간선이 없는 경우는 잘못된 답을 리턴하게 됨!

생각해본 반례는 요거다.

n : 3

computers : [[1, 0, 0], [0, 1, 1], [0, 1, 1]]

결과 : 2

 

그래서 위의 로직에서 모든 노드에 대해 bfs를 돌도록 수정함

 

문제 풀이

python

import heapq
def solution(n, computers):
    arr = [[] for _ in range(n+1)]
    nodes = [0 for _ in range(n+1)]
    
    for i in range(len(computers)) :
        for j in range(len(computers[i])) :
            if i != j and computers[i][j] == 1 :
                arr[i+1].append(j+1)
    
    def bfs(start) :
        nodes[start] = 1
        edge = 0
        q = []
        heapq.heappush(q,start)
        
        while q :
            front = heapq.heappop(q)
            for nx in arr[front] :
                if nodes[nx] != 1 :
                    nodes[nx] = 1
                    edge += 1
                    heapq.heappush(q, nx)
        return edge
                
    for i in range(n) :
        n -= bfs(i)
    return n

 

시간복잡도 O(N^2)

n <= 200

 

회고 및 느낀점

문제는 늘 꼼꼼히~