www.acmicpc.net/problem/13549

 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

문제 해결을 위한 과정

이 문제의 경우 BFS를 이용하면 해결할 수 있는 문제였습니다. 보통 BFS 문제의 경우 이차원 리스트 혹은 이차원 배열에서 특정 지점에서 다른 지점으로 퍼져나가는 형식으로 탐색하는 것인데 특이하게 이 문제의 경우 일차원 리스트상에서 해결해야 하기 때문에 처음에는 생각하기가 조금 어려웠던 문제였습니다.

먼저 문제의 예시를 살펴보도록 하겠습니다.

5의 위치에서 시작하여 17까지 가야합니다. 시간이 걸리지 않는 순간이동의 방식으로 현재 위치 * 2 한 지점으로 이동할 수 있습니다. 또는 시간이 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, m = map(int, input().split())
max = 100001
visited = [0] * max
move = [-1, 1]
 
def bfs():
    q = deque()
    q.append(n)
    count = 0
    visited[n] = 1
    if 2*n < max and not visited[2*n]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우 순간이동으로 탐색
        visited[2*n] = 1
        q.append(2*n)
    if visited[m] != 0: # 도착점인 경우 
        print(visited[m] - 1)
        return
    while q:
        pos = q.popleft()
        if visited[m] != 0: # 도착점인 경우
            print(visited[m] - 1)
            return
        if 2*pos < max and not visited[2*pos]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우
            visited[2*pos] = visited[pos] # 순간이동으로 탐색
            q.append(2*pos)
        for i in range(2): # 시간을 1초 소비하며 좌, 우를 탐색하는 경우
           npos = pos + move[i]
           if 0 <= npos < max:
               if not visited[npos]:
                   visited[npos] = visited[pos] + 1
                   q.append(npos)
 
bfs()
 
 cs

 

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

백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23
백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21
백준 알고리즘 1074: Z(Python)  (0) 2021.02.20

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/1475

 

1475번: 방 번호

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 키 포인트는 9와 6이 서로 뒤집을 수 있다는 것입니다. 그 숫자들을 제외하고는 숫자의 개수만큼 세트의 개수가 증가하기 때문에 고려하기 쉽습니다. 따라서 0부터 9까지 0으로 초기화된 리스트를 선언하고 6, 9는 더 작은 인덱스 번째를 증가시켜주고 그 외의 숫자는 해당 인덱스의 값을 증가시켜주는 방법을 통하면 쉽게 계산할 수 있습니다.

35996가 입력으로 주어진다고 가정하면 3번째 인덱스 5번째 인덱스의 값을 각각 증가시킵니다. 이를 그림으로 표현하면 다음과 같습니다.

0 0 0 0 0 0 0 0 0 0

초기 상태

 

0 0 0 1 0 1 0 0 0 0

3번째와 5번째를 하나씩 증가시킨 후

 

0 0 0 1 0 1 1 0 0 0

9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 인덱스를 증가시킴 편의상 낮은 인덱스를 증가시킴

 

0 0 0 1 0 1 1 0 0 1

9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 9번째 인덱스를 증가시킴 

 

0 0 0 1 0 1 2 0 0 1

6이 왔으므로 6번째 인덱스와 9번째 인덱스 중 더 작은 값을 가지는 6번째 인덱스를 증가시킴

 

이렇게 각 인덱스를 증가시키는 과정이 끝난 후 리스트에서 최댓값을 출력하면 필요한 세트의 수가 나오는 것을 알 수 있다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
word = input()
ans = [0] * 10
for i in range(len(word)):
    num = int(word[i])
    if num == 6 or num == 9:
        if ans[6] <= ans[9]:
            ans[6] += 1
        else:
            ans[9] += 1
    else:
        ans[num] += 1
 
print(max(ans))
 cs

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

백준 알고리즘 14503: 로봇 청소기(Python)  (0) 2021.02.03
백준 알고리즘 10773: 제로(Python)  (0) 2021.02.03
백준 알고리즘 7568: 덩치(Python)  (0) 2021.02.03
백준 알고리즘 1966: 프린터 큐(Python)  (0) 2021.02.02
백준 알고리즘 1316: 그룹 단어 체커(Python)  (0) 2021.02.02

www.acmicpc.net/problem/1316

 

1316번: 그룹 단어 체커

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 문제를 잘 보면 알 수 있는 점이 있습니다. abcd와 같이 뒤에 나오는 문자들이 전부 다 처음 나오는 문자이면 이는 그룹 단어로 인정하지만 abca같이 이미 나왔던 a가 뒤에 한번 더 나오는 경우는 그룹 단어로 인정하지 않는다는 것입니다. 따라서 먼저 알파벳의 개수인 26만큼의 0으로 초기화된 일차원 배열을 생성합니다. 그 후 단어들을 한 글자씩 조회를 합니다. 이 한 글자씩 조회된 문자를 아스키코드로 바꿔주어서 해당하는 배열의 인덱스 값이 0이면 1로 바꾸어 주고 이미 1로 되어있다면 즉 이미 앞에서 나왔던 단어인 경우 바로 break를 해줍니다. 

또한 abbbbbc와 같이 b가 여러개 있는 경우도 그룹 단어 이므로 위에서 말한 조건은 앞의 글자와 뒤의 글자가 다를 때만 적용해주는 걸로 쉽게 해결할 수 있습니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = int(input())
data = []
for i in range(n):
    data.append(input())
 
count = 0
for word in data:
    word += "!"
    alpha = [0] * 26
    check = True
    for i in range(len(word)-1):
        if word[i] != word[i+1]:
            if alpha[ord(word[i]) - 97] == 0:
                alpha[ord(word[i]) - 97] = 1
            else:
                check = False
                break
    if check:
        count += 1
 
print(count)
 cs

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

백준 알고리즘 7568: 덩치(Python)  (0) 2021.02.03
백준 알고리즘 1966: 프린터 큐(Python)  (0) 2021.02.02
백준 알고리즘 1152: 단어의 개수(Python)  (0) 2021.02.02
백준 알고리즘 2739: 구구단(Python)  (0) 2021.02.02
백준 알고리즘 2742: 기찍 N(Python)  (0) 2021.02.02

www.acmicpc.net/problem/2438

 

2438번: 별 찍기 - 1

첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제

www.acmicpc.net

문제 해결을 위한 과정

입력받은 n만큼 행과 열이 출력되므로 이차원 리스트를 이용하여 해결한다.

소스코드

 

1
2
3
4
5
6
n = int(input())
 
for i in range(1, n + 1):
    for j in range(i):
        print("*", end="")
    print()
 cs

 

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

백준 알고리즘 2741: N 찍기(Python)  (0) 2021.02.02
백준 알고리즘 2439: 별 찍기 - 2(Python)  (2) 2021.02.02
백준 알고리즘 15903: 카드 합체 놀이(Python)  (0) 2021.01.25
백준 알고리즘 2606: 바이러스(Python)  (0) 2021.01.25
백준 알고리즘 2667: 단지번호붙이기 (Python)  (0) 2021.01.25

https://www.acmicpc.net/problem/2178

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 BFS를 잘 숙지하고 암기하고 있다면 실버 1 티어라는 높은 난이도에도 불구하고 매우 쉽게 해결할 수 있는 문제였습니다. 1은 이동할 수 있는 칸이고 0은 이동할 수 없는 칸입니다. 또한 인접한 칸 즉 상, 하, 좌, 우 의 방향으로 이동하기 때문에 행, 열의 리스트를 각각 만들어서 다음과 같이 정의합니다.

 

dx = [-1, 1, 0, 0]

dy = [0, 0, -1 ,1]

 

위 처럼 정의하면 i = 0인 경우 (-1, 0) 즉 위쪽 방향(상), i = 1인 경우 (1, 0) 즉 아래쪽 방향(하), i = 2인 경우 (0, -1) 즉 좌측 방향(좌), i = 3인 경우 (0, 1) 즉 우측 방향(우)으로 for문을 이용하여 쉽게 해결할 수 있습니다.

 문제 해결을 위한 팁

위 문제의 경우 visited 리스트를 따로 정의하지 않아도 해결할 수 있습니다. 출발지와 도착지를 출발한 개수를 구하라고 하였기 때문에 bfs과정에서 방문하지 않은 그래프를 탐색하는것이 아닌 graph[nx][ny] == 1을 탐색하고 이 경우 이전 좌표의 그래프 값에 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
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
  graph.append(list(map(int, input())))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs(start):
  xPos = start[0]
  yPos = start[1]
  q = deque()
  q.append((xPos, yPos))
  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:
          graph[nx][ny] = graph[x][y] + 1
          q.append((nx, ny))
 
bfs((0, 0))
print(graph[n-1][m-1])
 cs

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

백준 알고리즘 2606: 바이러스(Python)  (0) 2021.01.25
백준 알고리즘 2667: 단지번호붙이기 (Python)  (0) 2021.01.25
백준 알고리즘 1260: DFS와 BFS (Python)  (0) 2021.01.19
백준 알고리즘 2810: 컵홀더 (Python)  (0) 2021.01.19
백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19

https://www.acmicpc.net/problem/1260

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 제가 전에 포스팅했던 DFS https://bgspro.tistory.com/14?category=981927,                                 BFS https://bgspro.tistory.com/15?category=981927를 정확하게 숙지 및 암기하고 있다면 실버 2 티어와 정답률 33프로의 문제임에도 불구하고 굉장히 쉽게 해결할 수 있는 문제입니다. 먼저 문제를 보겠습니다. 문제에서 그래프가 주어지고 이를 DFS로 탐색하는 경우 그리고 BFS로 탐색하는 경우를 출력하면 정답 판정을 받을 수 있습니다.

dfs와 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
from collections import deque
 
n, m, v = map(int, input().split())
graph = [[] for _ in range(1+n)]
visited = [0] * (1+n)
 
for i in range(m):
  a, b = map(int, input().split())
  # 양방향 연결
  graph[a].append(b)
  graph[b].append(a)
 
for i in range(n+1):
  graph[i].sort() # 연결된 노드가 여러곳일 경우 낮은 숫자를 가진 노드부터 탐색하기 위해 오름차순으로 
 
def dfs(graph, visited, v):
  print(v, end=" ")
  visited[v] = 1
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, visited, i)
 
def bfs(graph, visited, start):
  q = deque()
  q.append(start)
  visited[start] = 1
  while q:
    v = q.popleft()
    print(v, end= " ")
    for i in graph[v]:
      if not visited[i]:
        q.append(i)
        visited[i] = 1
 
dfs(graph, visited, v)
visited = [0] * (1+n)
print()
bfs(graph, visited, v)
 
 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
#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
 
vector<int> graph[MAX];
bool visited[MAX]; // false 초기화
bool visited2[MAX];
 
void dfs(int x) {
    visited[x] = true;
    printf("%d ", x);
 
    for (int i = 0; i < graph[x].size(); i++) {
        int y = graph[x][i];
        if (!visited[y]) {
            dfs(y);
        }
    }
}
 
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited2[start] = true;
 
    while (!q.empty()) {
        int x = q.front();
        printf("%d ", x);
        q.pop();
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited2[y]) {
                q.push(y);
                visited2[y] = true;
            }
        }
    }
}
 
int main(void) {
    int n, m, v;
    scanf("%d %d %d", &n, &m, &v);
 
    for (int i = 1; i < m + 1; 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());
    }
 
    dfs(v);
    printf("\n");
    bfs(v);
    return 0;
}
 cs

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

백준 알고리즘 2667: 단지번호붙이기 (Python)  (0) 2021.01.25
백준 알고리즘 2178: 미로 탐색 (Python)  (0) 2021.01.19
백준 알고리즘 2810: 컵홀더 (Python)  (0) 2021.01.19
백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19
백준 알고리즘 1715: 카드 정렬하기 (Python)  (0) 2021.01.11

+ Recent posts

티스토리툴바