www.acmicpc.net/problem/1068

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 DFS 카테고리에 있었던 깊이 우선 탐색 방식으로 해결할 수 있었던 문제입니다. 저는 처음에 tree구조를 직접 정의하여 해결하려 했으나 복잡하게 해결하는 것 같아 트리를 구현하는 방식이 아닌 단순하게 리스트에 그래프를 삽입하고 dfs를 이용하여 해결하는 기본적인 방식으로 해결하였습니다. 

문제의 예제 2번을 기준으로 설명드리겠습니다. -1 0 0 1 1 인데 0번째 노드는 root노드이므로 따로 빼두고 나머지 경우를 보겠습니다. 그 후 노드 1을 제거합니다. 그 과정은 다음 그림과 같습니다.

좌측은 1을 제거하기전 우측은 1을 제거한 후입니다. 리프 노드가 3개에서 1개로 감소한 것을 알 수 있습니다.

따라서 문제에서 주어진 노드부터 차례차례 삭제를 해 나아간 후(dfs를 응용한 remove함수로 구현) dfs를 이용해 리프 노드의 개수를 세주면 됩니다.

문제 해결을 위한 과정

위의 과정에 단 한가지 예외가 붙는데 바로 루트 노드를 삭제하는 경우입니다. 처음 입력받을 때 루트 노드를 따로 뺀 후 삭제를 시작할 입력받은 노드가 루트 노드라면 바로 0을 출력해주면 됩니다. 이유는 루트 노드를 삭제하는 경우 전체 노드가 없어지기 때문입니다.

소스코드 
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
import copy
n = int(input())
graph = [[] for _ in range(n+1)]
data = list(map(int, input().split()))
for i in range(n):
    if data[i] == -1: # 부모가 -1인 경우 루트노드로 설정
        root = i
        continue
    graph[data[i]].append(i) # 루트노드가 아닌경우 해당 그래프의 점에 연결
start = int(input())
 
def dfs(graph, visited, v): # dfs 방식으로 탐색
    global count
    visited[v] = True # 방문처리
    if len(graph[v]) == 0: # 리프 노드의 개수를 셈
        count += 1
    for i in graph[v]: # 방문처리하지 않은 노드를 재귀의 방식으로 dfs 탐색
        if not visited[i]:
            dfs(graph, visited, i)
    return count
 
def remove(tempgraph, graph, visited, v): # 입력받은 수의 자식노드를 제거해나가는 함수 dfs 방식 응용
    visited[v] = True
    for i in range(n): # 그래프를 조회하며 dfs 방식으로 탐색한 노드들을 tempgraph에서 삭제
        for j in range(len(graph[i])):
            if graph[i][j] == v:
                tempgraph[i].remove(v)
    for i in graph[v]:
        if not visited[i]:
            remove(tempgraph, graph, visited, i)
 
if start != root: # 지우기 시작할 노드가 root가 아닌경우
    tempgraph = copy.deepcopy(graph) # graph를 복사하여 tempgraph생성
    count = 0
    visited = [0] * (1 + n)
    remove(tempgraph, graph, visited, start)
 
    count = 0
    visited = [0] * (1 + n)
    print(dfs(tempgraph, visited, root))
else: # 지우기 시작할 노드가 root인 경우 그냥 0을 출력함
    print(0)
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23
백준 알고리즘 1074: Z(Python)  (0) 2021.02.20
백준 알고리즘 13459: 구슬 탈출(Python)  (0) 2021.02.19
백준 알고리즘 13460: 구슬 탈출 2 (Python)  (1) 2021.02.19

www.acmicpc.net/problem/1074

 

1074번: Z

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 전형적인 재귀, 분할 정복으로 해결할 수 있는 문제였습니다. 입력받은 좌표가 전체 영역에서 어떤 사분면에 위치하는지 파악 후 이들을 분할한 뒤 또 어떤 사분면에 해당하는지 위치를 알아가면 해결할 수 있는 문제였습니다.

그림으로 설명하겠습니다. 

 

n이 3인 경우를 예로 들겠습니다.

4행 6열즉 52가 몇 번째로 탐색이 되는지 판단해봅시다. (이미 52라 나와있긴 합니다만...)

우선 크게 4개의 사분면으로 쪼개면 해당 좌표는 4 사분면에 위치합니다. 그 후 쪼개면 다음 그림과 같습니다.  

이렇게 분할하면 이번에는 2 사분면에 위치하는 것을 알 수 있습니다. 그 후 한번 더 분할합니다.

이번에는 1 사분면에 위치하는 것을 알 수 있습니다. 정리해보면 4 사분면->2 사분면->1 사분면으로 이동한 것을 알 수 있고 n이 1인 경우이므로 여기서 분할은 종료가 됩니다.

맨 처음에 4 사분면에 위치하고 4행 6열이 그 다음에는 2사분면에 위치하고 0행 2열이 됩니다. 그 후 1사분면의 0행 0열로 위치가 바뀌므로 우리는 사분면을 나눌때마다 좌표를 재배치 해줘야하는것을 알 수 있습니다. 따라서 reallocate()를 정의하여 해결해줍니다.

문제 해결을 위한 팁

이번에는 reallocate함수를 자세하게 알아봅시다. 위의 예시를 그대로 이용하겠습니다.

4사분면에 위치한 4행 6열이 2 사분면으로 이동할 때 0행 2열이 되었습니다. 따라서 각각 4 만큼씩 줄어들었습니다.

이후 0행 2열이 0행 0열이 되었는데 이번에는 열만 2 만큼이 줄어든 것을 알 수 있습니다. 따라서 이를 일반화하면 다음과 같습니다.

 

1 사분면인 경우 -> 유지

2 사분면인 경우 -> 열 값만 2^(n-1)만큼 감소

3 사분면인 경우 -> 행 값만 2^(n-1)만큼 감소

4 사분면인 경우 -> 행 열 모두 2^(n-1)만큼 감소

소스코드
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
n, r, c = map(int, input().split())
def find(r, c): # 사분면 찾는 함수
    if 0 <= r < 2 ** (n-1) and 0 <= c < 2 ** (n-1):
        return 1
    elif 0 <= r < 2 ** (n-1) and 2 ** (n-1) <= c < 2 ** (n):
        return 2
    elif 2 ** (n-1) <= r < 2 ** (n) and 0 <= c < 2 ** (n-1):
        return 3
    else:
        return 4
 
def reallocate(): # 사분면을 쪼갠후 좌표값을 재배치
    global r, c, n
 
    if res == 2: # 2사분면인 경우
        c -= 2 ** (n-1)
    elif res == 3: # 3사분면인 경우
        r -= 2 ** (n-1)
    elif res == 4: # 4사분면인 경우
        r -= 2 ** (n-1)
        c -= 2 ** (n-1)
    n -= 1
 
ans = 0
while True:
    if n <= 0:
        break
    res = find(r, c)
    ans = ans + (res-1) * (4 ** (n-1))
    reallocate()
 
print(ans)
 
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23
백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21
백준 알고리즘 13459: 구슬 탈출(Python)  (0) 2021.02.19
백준 알고리즘 13460: 구슬 탈출 2 (Python)  (1) 2021.02.19
백준 알고리즘 9012: 괄호 (Python)  (0) 2021.02.06

www.acmicpc.net/problem/13459

 

13459번: 구슬 탈출

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 전에 포스팅한 백준 알고리즘 13460번에서 10회 이하로 움직여서 구멍에 들어가는 것이 가능한 경우 횟수를 출력하는 것이 아닌 1을 출력, 불가능할 경우 -1을 출력하는 것이 아닌 0을 출력하는 것으로 하면 됩니다. 따라서 13460번 링크를 청부합니다.

 

백준 알고리즘 13460: 구슬 탈출 2 (Python)

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열..

bgspro.tistory.com

소스코드
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
from collections import deque
import sys
input = sys.stdin.readline # 빠른 입출력 위한 코드
 
n, m = map(int, input().split())
graph = []
for i in  range(n):
    graph.append(list(input()))
    for j in range(m):
        if graph[i][j] == 'R': # 빨간구슬 위치
            rx, ry = i, j
        elif graph[i][j] == 'B': # 파란구슬 위치
            bx, by = i, j
 
# 상 하 좌 우로 탐색
dx = [-1, 1, 0, 0]
dy = [0, 0, -1 ,1]
 
def bfs(rx, ry, bx, by):
    q = deque()
    q.append((rx, ry, bx, by))
    visited = [] # 방문여부를 판단하기 위한 리스트
    visited.append((rx, ry, bx, by))
    count = 0
    while q:
        for _ in range(len(q)):
            rx, ry, bx, by = q.popleft()
            if count > 10: # 움직인 횟수가 10회 초과면 -1 출력
                print(0)
                return
            if graph[rx][ry] == 'O': # 현재 빨간 구슬의 위치가 구멍이라면 count출력
                print(1)
                return 
            for i in range(4): # 4방향 탐색
                nrx, nry = rx, ry
                while True: # #일 때까지 혹은 구멍일 때까지 움직임
                    nrx += dx[i]
                    nry += dy[i]
                    if graph[nrx][nry] == '#': # 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
                        nrx -= dx[i]
                        nry -= dy[i]
                        break
                    if graph[nrx][nry] == 'O':
                        break
                nbx, nby = bx, by
                while True: # #일 때까지 혹은 구멍일 때까지 움직임
                    nbx += dx[i]
                    nby += dy[i]
                    if graph[nbx][nby] == '#': # 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
                        nbx -= dx[i]
                        nby -= dy[i]
                        break
                    if graph[nbx][nby] == 'O':
                        break
                if graph[nbx][nby] == 'O': # 파란구슬이 먼저 구멍에 들어가거나 동시에 들어가면 안됨 따라서 이 경우 무시
                    continue
                if nrx == nbx and nry == nby: # 두 구슬의 위치가 같다면
                    if abs(nrx - rx) + abs(nry - ry) > abs(nbx - bx) + abs(nby - by): # 더 많이 이동한 구슬이 더 늦게 이동한 구슬이므로 늦게 이동한 구슬 한칸 뒤로 이동
                        nrx -= dx[i]
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]
                if (nrx, nry, nbx, nby) not in visited: # 방문해본적이 없는 위치라면 새로 큐에 추가 후 방문 처리
                    q.append((nrx, nry, nbx, nby))
                    visited.append((nrx, nry, nbx, nby))
        count += 1
    print(0) # 10회가 초과하지 않았지만 10회 내에도 구멍에 들어가지 못하는 경우
bfs(rx, ry, bx, by)
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21
백준 알고리즘 1074: Z(Python)  (0) 2021.02.20
백준 알고리즘 13460: 구슬 탈출 2 (Python)  (1) 2021.02.19
백준 알고리즘 9012: 괄호 (Python)  (0) 2021.02.06
백준 알고리즘 9095: 1, 2, 3 더하기(Python)  (0) 2021.02.06

www.acmicpc.net/problem/13460

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 저는 BFS를 이용하여 해결하였습니다. 삼성 기출문제의 특성상 구현 즉 시뮬레이션 유형도 포함이 되어있는 문제였습니다. 고민을 많이 해결했던 문제지만 해결을 한 뒤에 생각해보면 그다지 어렵지는 않은 문제라 생각되기 때문에 구현 유형을 더 많이 공부해야겠다고 느낍니다. 

먼저 그래프를 입력받을 때 빨간 구슬의 위치와 파란 구슬의 위치를 각각 rx, ry, bx, by로 지정해줍니다. 그 후 bfs를 수행하는데 먼저 rx, ry, bx, by를 큐에 넣어주고 방문처리를 해줍니다. 구슬이 한번 움직이면 멈추는 경우는 2가지입니다.

1. 움직인 곳이 벽 # 인 경우

2. 구멍인 경우

따라서 이 2가지인 경우를 제외하고는 계속 움직일 수 있으므로 while True를 이용해 움직여 줍니다. 단 1번의 경우 방향을 유지하면서 한 칸 뒤로 이동해야 구슬의 현재 위치가 벽이 아니겠죠.

이 과정을 빨간 구슬과 파란 구슬 모두 수행해줍니다. 단 파란 구슬이 구멍에 들어간 경우 2가지의 상황이 존재하는데 

1. 빨간 구슬 파란 구슬 모두 구멍에 들어간 경우

2. 파란 구슬만 구멍에 들어간 경우

입니다. 그러나 이 2가지의 경우는 모두 문제에서 안된다고 조건이 있기 때문에 이 경우를 무시하기 위해 continue를 해줍니다. 그 외에 두 구슬이 같은 위치에 있다면 이 역시 문제에서 안 되는 조건이므로 더 많이 이동한 구슬 즉 더 늦게 이동한 구슬을 방향을 그대로 유지한 채로 한 칸 뒤로 움직여 줍니다.

소스코드
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
from collections import deque
import sys
input = sys.stdin.readline # 빠른 입출력 위한 코드
 
n, m = map(int, input().split())
graph = []
for i in  range(n):
    graph.append(list(input()))
    for j in range(m):
        if graph[i][j] == 'R': # 빨간구슬 위치
            rx, ry = i, j
        elif graph[i][j] == 'B': # 파란구슬 위치
            bx, by = i, j
 
# 상 하 좌 우로 탐색
dx = [-1, 1, 0, 0]
dy = [0, 0, -1 ,1]
 
def bfs(rx, ry, bx, by):
    q = deque()
    q.append((rx, ry, bx, by))
    visited = [] # 방문여부를 판단하기 위한 리스트
    visited.append((rx, ry, bx, by))
    count = 0
    while q:
        for _ in range(len(q)):
            rx, ry, bx, by = q.popleft()
            if count > 10: # 움직인 횟수가 10회 초과면 -1 출력
                print(-1)
                return
            if graph[rx][ry] == 'O': # 현재 빨간 구슬의 위치가 구멍이라면 count출력
                print(count)
                return 
            for i in range(4): # 4방향 탐색
                nrx, nry = rx, ry
                while True: # #일 때까지 혹은 구멍일 때까지 움직임
                    nrx += dx[i]
                    nry += dy[i]
                    if graph[nrx][nry] == '#': # 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
                        nrx -= dx[i]
                        nry -= dy[i]
                        break
                    if graph[nrx][nry] == 'O':
                        break
                nbx, nby = bx, by
                while True: # #일 때까지 혹은 구멍일 때까지 움직임
                    nbx += dx[i]
                    nby += dy[i]
                    if graph[nbx][nby] == '#': # 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
                        nbx -= dx[i]
                        nby -= dy[i]
                        break
                    if graph[nbx][nby] == 'O':
                        break
                if graph[nbx][nby] == 'O': # 파란구슬이 먼저 구멍에 들어가거나 동시에 들어가면 안됨 따라서 이 경우 무시
                    continue
                if nrx == nbx and nry == nby: # 두 구슬의 위치가 같다면
                    if abs(nrx - rx) + abs(nry - ry) > abs(nbx - bx) + abs(nby - by): # 더 많이 이동한 구슬이 더 늦게 이동한 구슬이므로 늦게 이동한 구슬 한칸 뒤로 이동
                        nrx -= dx[i]
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]
                if (nrx, nry, nbx, nby) not in visited: # 방문해본적이 없는 위치라면 새로 큐에 추가 후 방문 처리
                    q.append((nrx, nry, nbx, nby))
                    visited.append((nrx, nry, nbx, nby))
        count += 1
    print(-1) # 10회가 초과하지 않았지만 10회 내에도 구멍에 들어가지 못하는 경우
bfs(rx, ry, bx, by)
 
 cs
소스코드 - c++
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
#define MAX 11
using namespace std;
int n, m;
char graph[MAX][MAX];
int visited[MAX][MAX][MAX][MAX];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int rx, ry, bx, by;
 
int bfs(int x1, int y1, int x2, int y2) {
    queue<pair<int, int>> q1;
    queue<pair<int, int>> q2;
    q1.push(make_pair(x1, y1));
    q2.push(make_pair(x2, y2));
    visited[x1][y1][x2][y2] = 1;
    int count = 0;
 
    while (!q1.empty()) {
        int len = q1.size();
        for (int i = 0; i < len; i++) {
            int rx = q1.front().first;
            int ry = q1.front().second;
            int bx = q2.front().first;
            int by = q2.front().second;
            q1.pop();
            q2.pop();
            for (int j = 0; j < 4; j++) {
                int nrx = rx;
                int nry = ry;
                int nbx = bx;
                int nby = by;
                while (true) {
                    nrx = nrx + dx[j];
                    nry = nry + dy[j];
                    if (nrx < 0 || nry < 0 || nrx >= n || nry >= m) {
                        continue;
                    }
                    if (graph[nrx][nry] == '#') {
                        nrx = nrx - dx[j];
                        nry = nry - dy[j];
                        break;
                    }
                    else if (graph[nrx][nry] == 'O') {
                        break;
                    }
                }
                while (true) {
                    nbx = nbx + dx[j];
                    nby = nby + dy[j];
                    if (nbx < 0 || nby < 0 || nbx >= n || nby >= m) {
                        continue;
                    }
                    if (graph[nbx][nby] == '#') {
                        nbx = nbx - dx[j];
                        nby = nby - dy[j];
                        break;
                    }
                    else if (graph[nbx][nby] == 'O')
                        break;
                }
                if (graph[nbx][nby] == 'O') {
                    continue;
                }
                if (nrx == nbx && nry == nby) {
                    if (graph[nbx][nby] == 'O')
                        break;
                    else {
                        if (abs(rx - nrx) + abs(ry - nry) < abs(bx - nbx) + abs(by - nby)) {
                            nbx = nbx - dx[j];
                            nby = nby - dy[j];
                        }
                        else {
                            nrx = nrx - dx[j];
                            nry = nry - dy[j];
                        }
                    }
                }
                if (graph[nrx][nry] == 'O' && graph[nbx][nby] != 'O') {
                    if (count + 1 > 10)
                        continue;
                    return count + 1;
                }
                if (visited[nrx][nry][nbx][nby] == 0) {
                    visited[nrx][nry][nbx][nby] = 1;
                    q1.push(make_pair(nrx, nry));
                    q2.push(make_pair(nbx, nby));
                }
            }
        }
        count += 1;
    }
    if (count > 10) {
        return -1;
    }
    return -1;
}
 
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> graph[i][j];
            if (graph[i][j] == 'R') {
                rx = i;
                ry = j;
            }
            else if(graph[i][j] == 'B') {
                bx = i;
                by = j;
            }
        }
    }
 
    cout << bfs(rx, ry, bx, by);
    return 0;
}
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1074: Z(Python)  (0) 2021.02.20
백준 알고리즘 13459: 구슬 탈출(Python)  (0) 2021.02.19
백준 알고리즘 9012: 괄호 (Python)  (0) 2021.02.06
백준 알고리즘 9095: 1, 2, 3 더하기(Python)  (0) 2021.02.06
백준 알고리즘 2468: 안전 영역(Python)  (2) 2021.02.05

www.acmicpc.net/problem/9012

 

9012번: 괄호

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 문자열 카테고리의 문제입니다. 괄호가 쌍으로 맞게 이루어져 있다면 YES를 출력 그렇지 않다면 NO를 출력하면 됩니다. count = 0을 선언한 후 "("인 경우 count += 1을 ")"인 경우 count -= 1을 해준다면 쉽게 해결할 수 있습니다.

 

1) 만일 count가 음수라면 )로 시작하거나 )의 개수가 (에 비해 더 많은 경우 즉 짝이 맞지 않으므로 NO를 출력합니다.

2) 만일 count가 0이 아닌 자연수인 경우 (의 개수가 )에 비해 더 많은 경우 즉 짝이 맞지 않으므로 NO를 출력합니다.

3) 만일 count가 0이라면 짝이 맞으므로 YES를 출력합니다. (단 1이 아닌 경우 )( 같은 경우를 제외시켜주기 위함)

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
tc = int(input())
for i in range(tc):
    a = input()
    ans = 0
    for i in range(len(a)):
        if a[i] == "(":
            ans += 1
        elif a[i] == ")":
            ans -= 1
        if ans < 0:
            break
    if ans == 0:
        print("YES")
    else:
        print("NO")
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 13459: 구슬 탈출(Python)  (0) 2021.02.19
백준 알고리즘 13460: 구슬 탈출 2 (Python)  (1) 2021.02.19
백준 알고리즘 9095: 1, 2, 3 더하기(Python)  (0) 2021.02.06
백준 알고리즘 2468: 안전 영역(Python)  (2) 2021.02.05
백준 알고리즘 11724: 연결 요소의 개수(Python)  (0) 2021.02.05

www.acmicpc.net/problem/9095

 

9095번: 1, 2, 3 더하기

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 각 숫자들의 규칙성을 찾는 게 가장 중요한 문제였습니다. 한번 규칙을 파악하고 나면 쉽게 해결할 수 있는 다이내믹 프로그래밍 유형의 문제입니다.

1 = 1, 즉 1가지

2 = 1 + 1,

      2, 즉 2가지

3 = 1 + 1 + 1,

      1 + 2, 2 + 1,

      3 즉 4가지

4 = 1 + 1 + 1+ 1,

      1 + 1 + 2, 1 + 2 + 1, 2 + 1+ 1,

      1 + 3, 3 + 1,

      2 + 2 즉 7가지

5 = 1 + 1 + 1 + 1 + 1,

      1 + 1 + 1 + 2, 1 + 1 + 2 + 1, 1 + 2 + 1 + 1,  2 + 1 + 1 + 1,

      1 + 2 + 2, 2 + 1 + 2, 2 + 2 + 1

      1 + 1 + 3, 1 + 3 + 1, 3 + 1 +1

      2 + 3,

      3 + 2 즉 13가지

6 = 1 + 1 + 1 + 1 + 1 + 1,

      1 + 1+ 2 + 2, 1 + 2 + 1+ 2, 1 + 2 + 2 + 1, 2 + 1 + 1 + 2,  2 + 1 + 2 + 1, 2 + 2 + 1 + 1, 

      1 + 1 + 1 + 1 + 2, 1 + 1+ 1+ 2 + 1, 1 + 1 + 2 + 1 + 1, 1 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1

      1 + 1 + 1 + 3, 1 + 1 + 3 + 1, 1 + 3 + 1 + 1, 3 + 1 + 1 + 1 

      1 + 2 + 3, 1 + 3 + 2, 2 + 1 + 3, 2 + 3 +1, 3 + 1 + 2, 3 + 2 + 1, 

      2 + 2 + 2,

      3 + 3 즉 24가지 

 

이를 표로 정리하면 다음과 같습니다. (예시에서 나온 7과 10의 경우도 포함시킴)

1 2 3 4 5 6 7 8 9 10
1 2 4 7 13 24 44     274

따라서 우리는 n번째 값은 n-1번째 + n-2번째 + n-3번째 값을 더한것임을 알 수 있습니다. (단 n >= 4)

소스코드
1
2
3
4
5
6
7
8
9
dp = [0] * (12) # n이 11까지 이므로 12번째 까지 리스트를 생성한 후 0으로 초기화
dp[1] = 1; dp[2] = 2; dp[3] = 4 # 
for i in range(4, 12):
  dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
tc = int(input())
for i in range(tc):
  n = int(input())
  print(dp[n])
 
cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 13460: 구슬 탈출 2 (Python)  (1) 2021.02.19
백준 알고리즘 9012: 괄호 (Python)  (0) 2021.02.06
백준 알고리즘 2468: 안전 영역(Python)  (2) 2021.02.05
백준 알고리즘 11724: 연결 요소의 개수(Python)  (0) 2021.02.05
백준 알고리즘 1012: 유기농 배추(Python)  (0) 2021.02.05

www.acmicpc.net/problem/2468

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 조금 특이하지만 BFS를 이용하면 해결할 수 있는 문제였습니다. 먼저 그래프를 입력받을 때 그래프의 원소들 중 최댓값 max를 확인합니다. 그 후 3중 for문을 이용하여 해결하는데 가장 바깥 for문은 0부터 max-1까지(max의 경우 모든 지역이 물에 잠기므로 안전영역이 무조건 0이다 따라서 확인할 필요가 없음)이고 그 안쪽 for문은 행과 열을 조회하는 이중 for문이다. 이렇게 조회를 하는데 방문하지 않은 지역이고 비가 온곳 보다 높은 지역이라면 bfs함수를 호출한다. 마찬가지로 bfs함수 역시 방문하지 않고 비가 온곳 보다 높은 지역을 너비 우선 탐색 방식으로 탐색한다. 

소스코드
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
from collections import deque
 
n = int(input())
graph = []
max = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] > max:
            max = graph[i][j] # 그래프의 원소들 중 최댓값을 찾음
 
def bfs(xPos, yPos, value, visited):
    q = deque()
    q.append((xPos, yPos))
    visited[xPos][yPos] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] > value and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
   
maximum = 0
for a in range(max): # 비가 안오는 경우인 0부터 max-1까지 조회(max는 모든 지역이 물에 잠기므로 안전영역이 0임 고려할 필요가 없음)
    visited = [[0] * n for _ in range(n)] # 매 높이마다 조회를 해야하므로 visited를 매번 정의
    ans = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] > a and visited[i][j] == 0: # 비가 온것보다 높은 곳이고 방문하지 않은 경우 bfs호출
                bfs(i, j, a, visited)
                ans += 1
    if maximum < ans:
        maximum = ans
print(maximum)
                
               
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 9012: 괄호 (Python)  (0) 2021.02.06
백준 알고리즘 9095: 1, 2, 3 더하기(Python)  (0) 2021.02.06
백준 알고리즘 11724: 연결 요소의 개수(Python)  (0) 2021.02.05
백준 알고리즘 1012: 유기농 배추(Python)  (0) 2021.02.05
백준 알고리즘 14503: 로봇 청소기(Python)  (0) 2021.02.03

www.acmicpc.net/problem/11724

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주

www.acmicpc.net

문제 해결을 위한 과정

위 문제는 이차원 리스트를 이용하는 것이 아닐 뿐 단순한 BFS알고리즘을 통해 해결할 수 있는 문제였습니다. 각각의 입력정보들을 입력받은 후 각 노드들에 대해서 방문처리하지 않았다면 BFS 함수를 호출하고 이때 호출된 횟수만큼을 출력해주면 되는 쉬운 문제였습니다.

소스코드
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
from collections import deque
 
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (1 + n)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
 
def bfs(graph, visited, start):
    q = deque()
    q.append(start)
    visited[start] = 1
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = 1
 
count = 0
for i in range(1, n + 1):
    if visited[i] == 0:
        bfs(graph, visited, i)
        count += 1
print(count)
 cs
소스코드 - python
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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define MAX 1001
 
using namespace std;
vector<int> graph[MAX];
bool visited[MAX];
 
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                visited[y] = true;
                q.push(y);
            }
        }
    }
}
 
int main(void) {
    int n, m;
    int count = 0;
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    for (int i = 1; i < n+1; i++) {
        sort(graph[i].begin(), graph[i].end());
    }
 
    for (int i = 1; i < n + 1; i++) {
        if (!visited[i]) {
            bfs(i);
            count += 1;
        }
    }
 
    printf("%d", count);
    return 0;
}
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 9095: 1, 2, 3 더하기(Python)  (0) 2021.02.06
백준 알고리즘 2468: 안전 영역(Python)  (2) 2021.02.05
백준 알고리즘 1012: 유기농 배추(Python)  (0) 2021.02.05
백준 알고리즘 14503: 로봇 청소기(Python)  (0) 2021.02.03
백준 알고리즘 10773: 제로(Python)  (0) 2021.02.03

+ Recent posts

티스토리툴바