백준 Online Judge 문제
체크리스트
✅ 해결 🟩 미해결 🟩 포기
풀이에 걸린 시간: 2시간
- 풀이가 떠오른 과정
🟩 문제를 읽고 주어진 시간제한과 메모리제한 내에서의 풀이가 떠올랐다.
✅ 문제를 읽고 시간제한과 메모리제한 내에서 해결이 가능한 지는 모르겠지만 풀이가 떠올랐다.
🟩 문제를 읽고 풀이가 떠오르지 않았다.
🟩 문제가 곧바로 이해되지 않았다.
- 풀이 작성 과정
✅ 풀이를 아무런 도움 없이 작성하였다.
🟩 풀이를 관련된 알고리즘 지식만을 찾아 숙지한 채 작성하였다.
🟩 풀이를 남의 정답코드를 찾아 참고하여 작성하였다.
🟩 알고리즘 개념에 대한 공부를 하다 해당 개념에 대한 문제를 찾았고, 풀었다.
알고리즘 개념
- 너비우선탐색(BFS,Breadth First Search)
- 클래스로 구현한 트리(Tree)
다른 방법으로도 풀이할 수 있겠지만, 자료구조를 연습하기 위해 푼 문제이기 때문에 class를 통해 직접 node와 tree 객체를 선언해서 이를 활용하여 문제를 해결하였다. - 해싱을 위한 딕셔너리(Dictonary)
입력의 갯수나 노드item의 구성을 잘 모르는 상태이기 때문에 어떤 입력이 들어와도 가공이 가능한 형태를 위해 딕셔너리를 사용해 노드의 item값을 입력하면 node에 직접참조할 수 있는 리스트를 만들었다.
풀이과정
- 입력 형태
일반적인 백준 문제 형태가 아닌, ICPC의 1997년 출제문제로 꽤나 오래된 출제형식의 입력 형태를 따르고 있어서, 입력내용을 가공하는 게 꽤나 귀찮았다. python으로 풀이하기에는 적합하지 않은 형태의 입력 형태인 것으로 보인다. 또한 변수의 범위나 입력으로 들어오는 케이스의 최대 갯수 등이 확정되지 않은 상태여서 시간제한과 메모리제한에 대하여 정확히 파악하기가 어려웠다. 시간복잡도나 공간복잡도를 효율적으로 낮추는 요즘 문제에 비해 구현에 중점을 두던 옛날 문제의 특징인 것 같다.
노드와 트리를 클래스를 통해 선언하고, 입력별로 case를 구분할 수 있는 흐름을 만들어준 다음에 케이스마다 그래프를 만들고 트리인지 아닌지 판별 후에 초기화 시키고 다음 케이스를 진행시키는 구성으로 구현하였다. - 트리인지, 아닌지
케이스 내에서 각 정점을 노드로 생성하고, 노드의 값으로 간선의 정보를 모두 입력해준 뒤에, 문제에서 주어진 트리의 조건을 활용하여 필터링하는 식으로 구현하였다.
- 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다.
모든 노드를 순회하며 들어오는 간선이 하나도 없는 노드를 루트로 지정하고, 만약 그 이후에도 들어오는 간선이 하나도 없는 노드를 발견하면, case false를 출력하고 case를 종료한다.
또한 들어오는 간선이 하나도 없는 노드가 단 한 개도 존재하지 않는다면, case false를 출력하고 case를 종료한다. - 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다.
모든 노드를 순회하며 루트 이외의 노드에 대하여 들어오는 간선이 하나 밖에 존재하지 않는지, 루트 노드에 대하여 들어오는 간선이 존재하지 않는지를 확인하여 이를 하나라도 어기면 case false를 출력하고 case를 종료한다.
- 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.
1번과 2번을 만족하면 '완전한 트리'와 '그래프 중 일부가 트리이고 그 트리에 간선으로 연결되지 않은 정점의 집합으로 이루어진 그래프'. 두 가지로 분류되는데, 후자를 분류하기 위하여 일단 트리를 선언해 루트부터 bfs로 트리의 모든 노드를 순회하여 만약 순회할 때 한 번이라도 방문하지 않은 노드가 존재한다면 후자라고 판단해 case false를 출력하고 case를 종료한다.
테스트케이스
이 문제에서는 노드가 없는 빈 그래프도 트리이다. 다음은 여러 예외처리를 위해서 활용했던 테스트케이스이다.
- input
1 2
2 3
3 2
4 5
0 0
0 0
1 2 2 1 0 0
1 2 0 0
1 1 0 0
6 8 5 3 5 2 6 4
5 6 0 0
8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0
3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1- output
Case 1 is not a tree.
Case 2 is a tree.
Case 3 is not a tree.
Case 4 is a tree.
Case 5 is not a tree.
Case 6 is a tree.
Case 7 is a tree.
Case 8 is not a tree.코드
from collections import deque
import sys;rl=sys.stdin.readline
caseCnt = 0
Lines = dict()
class Node():
def __init__(self,item:int):
self.item = item
self.canGoTo = []
self.canComeFrom = []
self.canFromRoot = False
class Tree():
def __init__(self,root:Node):
self.root = root
def levelorder(self,n:Node):
if n != None:
queue = deque()
queue.append(n)
while queue:
tmp = queue.popleft()
if tmp.canFromRoot == False:
tmp.canFromRoot = True
for item in tmp.canGoTo:
global nodes
queue.append(nodes[item])
while 1:
INP = rl().rstrip()
# -1 -1이 입력된 경우 입력종료
if INP == '-1 -1':
break
# 빈 줄이 입력된 경우 무시
elif INP == '':
continue
caseEnd = 0
inputLine = list(map(int,INP.split()))
# 입력으로 0 0이 들어올 때까지 간선 내용 저장
for i in range(0,len(inputLine),2):
if inputLine[i] == 0 and inputLine[i+1] == 0:
caseEnd = 1
break
elif inputLine[i] in Lines:
Lines[inputLine[i]].append(inputLine[i+1])
else:
Lines[inputLine[i]] = [inputLine[i+1]]
# 입력으로 0 0이 들어온 경우 case 결과 출력 후 입력 초기화
if caseEnd == 1:
caseCnt += 1
# key값이 node의 item인 node dict 생성
nodes = dict()
for key in Lines.keys():
#입력 내에서 간선의 출발점이 되는 정점을 노드로 추가
if not key in nodes.keys():
nodes[key] = Node(key)
for value in Lines[key]:
#입력 내에서 간선의 도착점이 되는 정점을 노드로 추가
if not value in nodes.keys():
nodes[value] = Node(value)
#정점으로 들어오는 간선 정보를 도착정점 노드에 추가
nodes[value].canComeFrom.append(key)
#정점에서 나가는 간선 정보를 출발정점 노드에 추가
nodes[key].canGoTo.append(value)
root = None
isTree = True
for nodeItem in nodes.keys():
# 1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 root노드라 부른다.
if len(nodes[nodeItem].canComeFrom) == 0:
if root == None:
root = nodeItem
# 만약 들어오는 간선이 하나도 없는 노드를 찾았는데 root가 이미 있으면, case를 false로 종료한다.
else:
isTree = False
break
# 만약 들어오는 간선이 하나도 없는 노드가 없다면, case를 false로 종료한다.
if root == None:
isTree = False
if isTree:
for nodeItem in nodes.keys():
# 2. 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다.
if len(nodes[nodeItem].canComeFrom) != 1 and nodeItem != root:
isTree = False
break
# 루트 노드로 들어오는 간선이 존재하면, case를 false로 종료한다.
if len(nodes[root].canComeFrom) > 0 :
isTree = False
# 3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.
# 1번과 2번을 만족하면, 일단 트리 형태를 만들 수 있는데, 3번 형태가 만족되지 않는 것은 트리에서 연결되지 않은 노드가 존재하지 않는다는 뜻이기 때문에, 트리를 순회하여 Node의 방문하게 되면 canFromRoot을 True값으로 변경하고, 순회가 종료된 뒤에 canFromRoot가 False인 Node가 존재하면 트리가 아니라고 출력한다.
if not any(Lines):
isTree = True
if isTree and any(Lines):
tree = Tree(nodes[root])
tree.levelorder(nodes[root])
for nodeItem in nodes.keys():
if nodes[nodeItem].canFromRoot == False:
isTree = False
break
#for nodeItem in nodes.keys():
# print(nodes[nodeItem].item,nodes[nodeItem].canGoTo,nodes[nodeItem].canComeFrom,nodes[nodeItem].canFromRoot)
if isTree:
print('Case ' + str(caseCnt) + ' is a tree.')
else:
print('Case ' + str(caseCnt) + ' is not a tree.')
Lines = dict()
DIVIDE AND CONQUER