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

www.acmicpc.net/problem/14503

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 전형적인 구현 알고리즘입니다. 문제의 조건을 잘 따라가기만 한다면 그다지 큰 어려움 없이 해결할 수 있는 문제입니다. 먼저 문제에서 그래프의 정보와 시작 지점을 입력받습니다. 그 후 방향을 좌측으로 돌린 후 해당 지역이 청소가 필요한 지역이면 청소를 하고 지점을 옮겨줍니다. 벽인 경우는 방향을 다시 좌측으로 돌려줍니다. 이렇게 4번 돌리게 되면 해당 지역 주변에는 청소할 수 있는 지점이 없기 때문에 방향을 유지한 채로 뒤로 후진합니다. 이것은

nx = x - dx[direction], ny = y - dy[direction]으로 구현합니다.

만약 4방향 모두 청소할 수 없는 칸이여서 후진해야 하는데 후진해야 할 칸이 벽이어서 후진할 수 없는 경우 종료하고 청소했던 칸의 숫자를 출력합니다.(소스코드에 주석을 첨부합니다.)

소스코드
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
n, m = map(int, input().split())
r, c, d = map(int, input().split())
 
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
 
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
 
def turn_left(): # 방향을 좌측으로 돌리는 함수 0인경우 3이 나온다. 1인 경우는 0이 나온다. 나머지도 마찬가지
    global d
    d = (d-1) % 4
 
count = 1
x, y = r, c
graph[x][y] = 2 # 방문처리를 2로 함
 
while True:
    check = False # 방문한 칸이 있는지 없는지 유뮤를 판단하기 위한 bool형 변수 check
    for i in range(4): # 4방향을 돌며
        turn_left()
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < n and 0 <= ny < m: # nx, ny가 그래프를 벗어나지 않는지 확인
            if graph[nx][ny] == 0: # 청소할 수 있는 칸인 경우
                count += 1
                graph[nx][ny] = 2 # 방문처리 해줌
                x, y = nx, ny
                check = True # check를 True로 바꾸어 주어 방문했음을 알림
                break
    if not check: # 4방향을 확인했음에도 청소할 공간이 없는 경우 후진
        nx = x - dx[d]
        ny = y - dy[d]
        if 0 <= nx < n and 0 <= ny < m: # nx, ny가 그래프를 벗어나지 않는지 확인
            if graph[nx][ny] == 2: # 2라면 즉 이미 청소한 칸인경우 후진
                x, y = nx, ny
            elif graph[nx][ny] == 1: # 1인경우 즉 벽인 경우 
                print(count)
                break
        else:
            print(count)
            break
 
 cs

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

백준 알고리즘 11724: 연결 요소의 개수(Python)  (0) 2021.02.05
백준 알고리즘 1012: 유기농 배추(Python)  (0) 2021.02.05
백준 알고리즘 10773: 제로(Python)  (0) 2021.02.03
백준 알고리즘 1475: 방 번호(Python)  (0) 2021.02.03
백준 알고리즘 7568: 덩치(Python)  (0) 2021.02.03

+ Recent posts

티스토리툴바