[TIL] 10일차

1. JAVA

• 과제의 요구사항에 맞게 나름대로 필드와 메소드를 구성해서 완성했다
• 상속을 사용했었는데, 애초에 설계한대로 자식 클래스별로 같은 필드라도 디폴트 값이 달라 각각 새롭게 정의하여 진행했을 때는 상속의 의미가 크지 않은 것으로 결론냈다
  • 중복 필드 매번 재정의
  • getter/setter 메소드 쓸데없이 중복
  • changeGas 메소드 쓸데없이 중복
• 이후에 슈퍼클래스를 추상화하면서 공통 기능에 대한 처리를 해보고, 최종적으로 인스턴스 생성할 때 디폴트 값(요금, 최대 승객 수, 속도)를 입력하게 했을 때 상속의 효과가 가장 큰 것으로 보였다
• 원래 대략 알고있던 인터페이스와 추상클래스의 용도나 차이에 대해 더 알게 되었다
  • 추상클래스: 미완성 설계도, 다중상속 불가 -> 자식에 공통기능 전파
  • 인터페이스: 껍데기, 다중적용 가능 -> 원하는 일부 클래스(특히 다른 부모를 둔)에 적용할 기능
• 본 과제에는 인터페이스가 크게 의미가 없어 적용하진 않았다
• JDK, JRE, JVM

What is the JDK? Introduction to the Java Development Kit

 

2. DFS 복습

 

207번

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)
        
        traced = set()
        def dfs(node):
            if node in traced: # 방문했던 노드에 다시 방문한다면 상태값 False
                return False
            
            traced.add(node) # 방문 사실 입력
            
            for next in graph[node]:
                if not dfs(next): # 자식 노드의 상태값이 False라면
                    return False # 부모 노드의 상태값도 False
                
            traced.remove(node) # 형제끼리 독립적으로 판단
            
            return True
            
        # 단 하나의 노드라도 상태값이 False (순환구조를 가짐)라면 정답은 False
        for node in list(graph):  # graph가 도중에 변하여 list(graph)로 탐색
            if not dfs(node):
                return False
            
        return True

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)
        
        traced = set()
        visited = set()
        
        def dfs(node):
            if node in traced: # 순환구조라면 False
                return False
            if node in visited: # 방문했던 노드면 True (가지치기)
                return True
            
            traced.add(node) # 방문 사실 입력
            
            for next in graph[node]:
                if not dfs(next): # 자식 노드의 상태값이 False라면
                    return False # 부모 노드의 상태값도 False
                
            traced.remove(node) # 탐색 종료 후 순환 노드 삭제
            visited.add(node) # 탐색 종료 후 방문 노드 추가 (탐색 중에 순환구조 발견될 수 있으므로 최후에 하는것이 나음)
            
            return True
            
        # 단 하나의 노드라도 상태값이 False (순환구조를 가짐)라면 정답은 False
        for node in list(graph): 
            if not dfs(node):
                return False
            
        return True

• 순환구조 판별할 때 탐색 후 traced에서 삭제하므로 그래프가 복잡할 때를 대비해 가지치기한다
• visited 집합으로 방문했던 노드를 추가하여 이미 방문했던 노드라면 탐색하지 않고 True 반환