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

www.acmicpc.net/problem/1012

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 전형적인 BFS알고리즘을 이용하면 쉽게 해결할 수 있는 문제였습니다. 먼저 문제의 입력 조건을 입력받은 후 n행 m열 그래프를 생성한 후 이중 for문을 이용하여 그래프의 값들을 조회해나가면서 BFS함수가 호출될 때마다 count를 하나 증가시켜주고 조회가 끝나면 count값을 출력해주면 됩니다. visited그래프를 생성하기보다는 탐색하면 graph[x][y]값을 2로 바꿔주면 보다 쉽게 해결할 수 있습니다. 

소스코드
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
from collections import deque
 
tc = int(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
for i in range(tc):
    n, m, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]
    for _ in range(k):
        a, b = map(int, input().split())
        graph[a][b] = 1
    
    def bfs(graph, xPos, yPos):
        q = deque()
        q.append((xPos, yPos))
        graph[xPos][yPos] = 2
        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 < m:
                    if graph[nx][ny] == 1:
                        q.append((nx, ny))
                        graph[nx][ny] = 2
    count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                bfs(graph, i, j)
                count += 1
    print(count)
 cs

 

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

백준 알고리즘 2468: 안전 영역(Python)  (2) 2021.02.05
백준 알고리즘 11724: 연결 요소의 개수(Python)  (0) 2021.02.05
백준 알고리즘 14503: 로봇 청소기(Python)  (0) 2021.02.03
백준 알고리즘 10773: 제로(Python)  (0) 2021.02.03
백준 알고리즘 1475: 방 번호(Python)  (0) 2021.02.03

+ Recent posts

티스토리툴바