반응형

문제


그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.


입력


첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.



백준에서 Queue로 분류가 되어있는 문제입니다. 이 문제를 풀때 Queue로 분류되어 있다고 Queue만 사용한다면 문제를 푸는데 조금 힘들 수 있습니다.

DFS(깊이 우선 탐색)의 경우 Stack, BFS(너비 우선 탐색)의 경우 Queue를 사용해서 풀면 간단하게 구현이 가능합니다.


DFS의 경우 Stack을 사용하는데, 각 노드를 방문하고 자식노드를 찾으러 가야하는 경우에 Stack의 현재 노드를 push해줍니다. 이후에 다시 이 노드로 돌아오게 되는 경우에 이 Stack에 저장된 값을 가지고 이 노드로 돌아와서 나머지 자식노드들을 탐색 할 수 있게 저장하는 것입니다.


BFS의 경우 Queue를 사용하는데, 노드를 방문할때마다 Queue에 저장을 합니다. 즉 현재 노드의 자식노드들을 전부 Queue에 push를 합니다. 모든 자식 노드를 push를 하였으면 Queue에서 pop해서 queue의 넣은 자식노드들 중 가장 먼저 넣었던 노드 번호를 꺼내오고 그 노드의 자식 노드를 전부 Queue의 넣습니다. 위 과정을 반복하면 너비 우선 탐색으로 모든 노드들을 탐색 할 수 있습니다.


코드

아래 코드의 경우 이전에 백준 문제를 풀며서 구현해놓은 Queue와 Stack을 사용하여 문제를 풀었습니다. Queue와 Stack의 push, pop이 어떤 상황에 쓰이는지 확인해보시고 문제를 풀면 도움이 될것 같네요. 

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Queue:
    def __init__(self):
        self.queue = []
 
    def push(self, num):
        self.queue.append(num)
 
    def pop(self):
        return self.queue.pop(0) if len(self.queue) != 0 else -1
 
    def size(self):
        return len(self.queue)
 
    def empty(self):
        return 1 if self.size() == 0 else 0
 
    def front(self):
        return self.queue[0] if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1] if self.size() != 0 else -1
 
class Stack:
    def __init__(self):
        self.list = []
 
    def push(self, num):
        self.list.append(num)
 
    def pop(self):
        if self.size() == 0:
            return -1
        return self.list.pop()
 
    def size(self):
        return len(self.list)
 
    def empty(self):
        return 1 if len(self.list) == 0 else 0
 
    def top(self):
        return self.list[-1] if self.size() != 0 else -1
 
node, edge, start = map(int, input().split())
 
#graph
graph =  [[0 for cols in range(node)]for rows in range(node)]
for _ in range(edge):
    source, target = map(int, input().split())
    graph[source-1][target-1] = 1
    graph[target-1][source-1] = 1
 
#dfs
stack = Stack()
dfs_visited_flag = [0 for clos in range(node)]
current_node = start-1
output = []
while(True):
    visit_count = 0
    if current_node + 1 not in output:
        output.append(current_node + 1)
        dfs_visited_flag[current_node] = 1
    for i in range(node):
        if graph[current_node][i] == 1 and dfs_visited_flag[i] != 1:
            stack.push(current_node + 1)
            current_node = i
            visit_count += 1
            break
    if visit_count == 0:
        current_node = stack.pop() - 1
 
    if current_node < 0:
        break
 
print(" ".join(str(x) for x in output))
 
#bfs
queue = Queue()
bfs_visited_flag = [0 for clos in range(node)]
queue.push(start)
current_node = start-1
bfs_visited_flag[current_node] = 1
output = []
while(True):
    for i in range(node):
        if graph[current_node][i] == 1 and bfs_visited_flag[i] != 1:
            queue.push(i+1)
            bfs_visited_flag[i] = 1
    output.append(queue.pop())
    current_node = queue.front()-1
    if current_node < 0:
        break
 
print(" ".join(str(x) for x in output))
 
cs


반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 11866, 1158 조세퍼스 문제 파이썬 구현  (0) 2019.01.13
[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.09
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.08
반응형

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력 1 

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1 

NO
NO
YES
NO
YES
NO


코드

스택을 이용하여 push pop을 통해 괄호의 짝을 찾을 수 있습니다.

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
38
39
40
41
42
43
44
45
46
47
48
49
50
class Stack:
    def __init__(self):
        self.list = []
 
    def push(self, num):
        self.list.append(num)
 
    def pop(self):
        if self.size() == 0:
            return -1
        return self.list.pop()
 
    def size(self):
        return len(self.list)
 
    def empty(self):
        return True if len(self.list) == 0 else False
 
    def top(self):
        return self.list[-1] if self.size() != 0 else -1
 
def isVaildParan(chars):
    stack = Stack()
    isVPS = True
    if len(chars) == 0:
        isVPS = False
 
    for i in range(len(chars)):
        if chars[-(i+1)] == ")":
            stack.push(chars[-(i+1)])
        else:
            if stack.pop() == -1:
                isVPS = False
 
    if not stack.empty() or not isVPS:
        return False
    else:
        return True
 
#몇개의 숫자를 받을건지
num = int(input())
 
#반복문을 통해 isValid~ 호출
for i in range(num):
    chars = list(input())
    if isVaildParan(chars):
        print("YES")
    else:
        print("NO")
 
cs


반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 1260 DFS와 BFS 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.08
[알고리즘] 백준 - 10828 스택 파이썬 구현  (0) 2019.01.07
반응형

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 먼저 들어간 자료가 제일 나중에 나오는 (FILO, first in last out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키 도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 

정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1 

8
4
3
6
8
7
5
2
1
예제 출력 1 
+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

예제 입력 2 

5
1
2
5
3
4

예제 출력 2 

NO

소스코드

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Stack:
    def __init__(self):
        self.list = []
 
    def push(self, num):
        self.list.append(num)
 
    def pop(self):
        if self.size() == 0:
            return -1
        return self.list.pop()
 
    def size(self):
        return len(self.list)
 
    def empty(self):
        return 1 if len(self.list) == 0 else 0
 
    def top(self):
        return self.list[-1] if self.size() != 0 else -1
 
#몇개의 숫자를 받을건지
num = int(input())
#문제를 풀기위해 사용한 stack
stack = Stack()
#입력을 저장하기 위한 list
inputs = []
#출력을 저장하기 위한 list
outputs = []
idx = 0
 
#입력을 받아 inputs 리스트에 저장
for i in range(num):
    inputs.append(int(input()))
 
#for loop를 돌며 각 loop의 시작에서 push를 하며 시작
for i in range(num):
    stack.push(i+1)
    outputs.append("+")
 
    #idx가 전체 숫자의 개수보다 큰 경우가 이 문제를 풀지 못하는경우
    #그러한 경우 발생시 while에서 pop을 하지 않기 떄문에 stack에 숫자가 남게됨
    while idx < num and stack.top() == inputs[idx]:
        stack.pop()
        outputs.append("-")
        idx += 1
 
#숫자가 남은 경우 이 문제를 풀지 못하는 경우 "NO"를 출력
if not stack.empty():
    print("NO")
else:
    for str in outputs:
        print(str)
 
cs


반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 1260 DFS와 BFS 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.09
[알고리즘] 백준 - 10828 스택 파이썬 구현  (0) 2019.01.07
반응형

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

  • push X: 정수 X를 스택에 넣는 연산이다.
  • pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 스택에 들어있는 정수의 개수를 출력한다.
  • empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
  • top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 

100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

반응형

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1 

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top
예제 출력 1 
2
2
0
2
1
-1
0
1
-1
0
3

 

예제 입력 2 
7
pop
top
push 123
top
pop
top
pop

예제 출력 2 

-1
-1
123
123
-1
-1

 

 
위 문제를 파이썬으로 구현한 결과입니다.
단, 다른 언어를 쓰는 분들도 참고 할 수 있도록 몇가지 파이썬 내장함수를 사용하지 않고 직접 구현하는 방법으로 진행하였습니다.
 
Stack 클래스를 정의해놨기 때문에 이후 다른 문제를 풀때 활용하면 되겠습니다.
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
38
39
40
41
42
43
44
45
46
47
48
#Stack class 정의
class Stack:
    def __init__(self):
        self.len = 0
        self.list = []
        
    def push(self, num):
        self.list.append(num)
        self.len += 1
    
    def pop(self):
        if self.size() == 0:
            return -1
        pop_result = self.list[self.len - 1]
        del self.list[self.len - 1]
        self.len -= 1
        return pop_result
        
    def size(self):
        return self.len
        
    def empty(self):
        return 1 if self.len == 0 else 0
        
    def top(self):
        return self.list[-1] if self.size() != 0 else -1
        
 
num = int(input())
stack = Stack()
while(num > 0):
    num -= 1
    input_split = input().split()
 
    op = input_split[0]
 
    if op == "push":
        stack.push(input_split[1])
    elif op == "pop":
        print(stack.pop())
    elif op == "size":
        print(stack.size())
    elif op == "empty":
        print(stack.empty())
    elif op == "top":
        print(stack.top())
    else:
        print("unacceptable op")
 cs

 

반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 1260 DFS와 BFS 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.09
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.08

+ Recent posts

티스토리툴바