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

 

1152번: 단어의 개수

첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 단어와 단어 사이에 공백이 있다는 점을 이용하여 해결을 합니다. 문제의 예시를 보면

The Curious Case of Benjamin Button 공백이 5개가 있습니다. 공백은 단어 사이에 존재하기 때문에 단어는 6개입니다.

그러나 예시 중 시작이 공백으로 시작하는 것이 있습니다. 이를 염두에 두면 단어 뒤에 공백이 존재하는 경우 단어의 개수를 하나 증가시키는 방향으로 해결할 수 있다는 것을 알 수 있습니다.

문제 해결을 위한 팁

문제 해결을 위한 과정을 보면 단어 다음에 공백이 있다면 단어의 개수를 하나 증가시키는 것으로 해결할 수 있다는 것을 알 수 있습니다. 그러나 이렇게 하면 문자열의 가장 마지막 단어의 개수를 셀 수 없게 됩니다. 따라서 단어를 입력받은 후 그 뒤에 공백 문자를 붙여주면 이 문제점을 해결할 수 있습니다.

소스코드

 

1
2
3
4
5
6
7
8
word = input()
word += " "
count = 0
for i in range(len(word)-1):
    if word[i] != " " and word[i+1] == " ":
        count += 1
 
print(count)
 cs

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

백준 알고리즘 1966: 프린터 큐(Python)  (0) 2021.02.02
백준 알고리즘 1316: 그룹 단어 체커(Python)  (0) 2021.02.02
백준 알고리즘 2739: 구구단(Python)  (0) 2021.02.02
백준 알고리즘 2742: 기찍 N(Python)  (0) 2021.02.02
백준 알고리즘 2741: N 찍기(Python)  (0) 2021.02.02

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

티스토리툴바