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

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

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 제가 예전에 포스팅한 BFS의 코드를 암기하고 숙지하고 있다면 쉽게 해결할 수 있는 문제였습니다. (https://bgspro.tistory.com/15?category=981927) 먼저 문제에서 입력으로 주어진 그래프를 생성합니다. 그 후 1번 노드에 대해서 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 = int(input())
m = int(input())
graph = [[] for _ in range(1 + n)]
visited = [False] * (1 + n)
 
for i in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
 
def bfs(graph, visited, start):
  global count
  q = deque([start])
  visited[start] = True
  while q:
    v = q.popleft()
    for i in graph[v]:
      if not visited[i]:
        q.append(i)
        visited[i] = True
        count += 1
 
count = 0
bfs(graph, visited, 1)
print(count)
 cs

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

백준 알고리즘 2438: 별 찍기 -1 (Python)  (0) 2021.02.02
백준 알고리즘 15903: 카드 합체 놀이(Python)  (0) 2021.01.25
백준 알고리즘 2667: 단지번호붙이기 (Python)  (0) 2021.01.25
백준 알고리즘 2178: 미로 탐색 (Python)  (0) 2021.01.19
백준 알고리즘 1260: DFS와 BFS (Python)  (0) 2021.01.19

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

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 난이도는 실버 1티어 이지만 DFS, BFS의 개념만 정확하게 알고 있으면 쉽게 해결할 수 있는 문제였습니다. 상, 하, 좌, 우 4가지 방향으로 움직일 수 있기 때문에 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]로 방향 리스트를 생성합니다. 그 후 bfs함수를 구현합니다. 

소스코드 - 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
from collections import deque
n = int(input())
graph = []
for i in range(n):
  graph.append(list(map(int, input())))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = []
cnt = 0
 
def bfs(xPos, yPos):
  count = 1
  q = deque()
  q.append((xPos, yPos))
  graph[xPos][yPos] = 0
  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] == 1:
          graph[nx][ny] = 0
          q.append((nx, ny))
          count += 1
  ans.append(count)
 
for i in range(n):
  for j in range(n):
    if graph[i][j] == 1:
      bfs(i, j)
      cnt += 1
 
ans.sort()
 
print(cnt)
for i in ans:
  print(i)
 
 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
#include <bits/stdc++.h>
#define MAX 26
 
using namespace std;
 
int graph[MAX][MAX];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
bool visited[MAX][MAX];
vector<int> vec;
 
void bfs(int xPos, int yPos, int n) {
    queue<pair<int, int>> q;
    q.push({ xPos, yPos });
    int count = 1;
    visited[xPos][yPos] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n or ny >= n)
                continue;
            if (graph[nx][ny] != 0 && visited[nx][ny] == false) {
                q.push({ nx, ny });
                count += 1;
                visited[nx][ny] = true;
            }
        }
    }
    vec.push_back(count);
}
 
int main(void) {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][j] != 0 && visited[i][j] == false) {
                bfs(i, j, n);
            }
        }
    }
 
    sort(vec.begin(), vec.end());
 
    printf("%d\n", vec.size());
    for (int i = 0; i < vec.size(); i++) {
        printf("%d\n", vec[i]);
    }
    return 0;
}
 cs

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

백준 알고리즘 15903: 카드 합체 놀이(Python)  (0) 2021.01.25
백준 알고리즘 2606: 바이러스(Python)  (0) 2021.01.25
백준 알고리즘 2178: 미로 탐색 (Python)  (0) 2021.01.19
백준 알고리즘 1260: DFS와 BFS (Python)  (0) 2021.01.19
백준 알고리즘 2810: 컵홀더 (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

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

 

18428번: 감시 피하기

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 BFS로 해결하기보다는 문제의 조건을 따라서 해결하면 더 쉬웠던 문제입니다. 처음에 그래프입력을 받으면서 x인 곳을 blank라는 리스트에 따로 추가하고 T인 곳을 teacher이라는 리스트에 따로 추가를 해줍니다. 선생님들은 상, 하 , 좌, 우 4곳으로 볼 수 있고 방해물이 없다면 그래프의 끝까지 조회할 수 있으므로 방향 리스트인 dx, dy를 만들고 bfs함수를 정의합니다. 각 방향을 끝까지 조회하면서 빈칸인 경우 T로 방문처리를 해주거나, 방해물이 있는경우 그 뒤쪽은 볼수 없는 경우를 처리해주고, 학생을 찾은 경우 바로 bfs함수에서 False를 return해주면 쉽게 해결할 수 있습니다. 학생을 찾지 못한 경우는 True를 return해주면 되겠습니다.

소스코드
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
from collections import deque
from itertools import combinations
import copy
 
n = int(input())
graph = []
teacher = []
blank = []
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
for i in range(n):
  graph.append(list(input().split()))
  for j in range(n):
    if graph[i][j] == 'T':
      teacher.append((i, j))
    elif graph[i][j] == "X":
      blank.append((i, j))
 
def bfs(): # 학생 찾으면 False 반환
  q = deque(teacher)
  test_graph = copy.deepcopy(graph)
  while q:
    x, y = q.popleft()
    for i in range(4):
      temp_x, temp_y = x, y
      while True:
        nx = temp_x + dx[i]
        ny = temp_y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
          if test_graph[nx][ny] == 'X':
            test_graph[nx][ny] = 'T'
          elif test_graph[nx][ny] == 'S':
            return False
          elif test_graph[nx][ny] == 'O':
            break
          temp_x, temp_y = nx, ny
        else:
          break
  return True
 
check = False
for data in list(combinations(blank, 3)):
  for x, y in data:
    graph[x][y] = 'O'
  if bfs():
    check = True
    break
  for x, y in data:
    graph[x][y] = 'X'
    
if check:
  print("YES")
else:
  print("NO")
 cs

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

백준 알고리즘 16234: 국영수(Python)  (0) 2020.12.09
백준 알고리즘 16234: 인구이동(Python)  (0) 2020.12.07
백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05
백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05
백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05

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

 

18405번: 경쟁적 전염

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 BFS만 알고 있다면 쉽게 해결할 수 있는 문제입니다. 그래프를 입력을 받을 때 0이 아닌 즉 바이러스가 있는 부분들에 대한 좌표를 따로 virus라는 리스트를 만들어서 그 리스트에 있는 좌표값들에 대해서만 BFS를 수행하면 되는 것입니다. 이때 문제에서 알 수 있듯이 이미 바이러스가 퍼진 구역에는 어떠한 바이러스도 퍼질 수 없으므로 그래프에서 해당 좌표의 지역이 0 인 경우 즉 비어있는 경우만 탐색을 할 수 있습니다. 또한 문제에서 숫자가 낮은 바이러스가 우선적으로 퍼지는 조건이 있습니다. 이 경우는 문제 해결을 위한 팁에서 알아보겠습니다.

문제 해결을 위한 팁

저의 경우는 바이러스가 있는 곳을 리스트에 넣을때 해당 좌표에 있는 바이러스에 값과 좌표를 리스트에 저장했습니다. 만약 입력 예시 1의 경우 0 행 0열에 있는 바이러스가 1 이기 때문에 virus.append((graph[i][j], i, j)) 이렇게 저장했습니다. 이 형태로 저장을 하게 되면 입력을 다 한 후 virus.sort()를 하게 되면 맨 앞 원소를 기준으로 오름차순으로 정렬을 하기 때문에 별도의 처리 없이 오름차순 된 virus 리스트 그대로 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
from collections import deque
 
N, K = map(int, input().split())
graph = []
virus = []
for i in range(N):
  graph.append(list(map(int, input().split())))
  for j in range(N):
    if graph[i][j] != 0:
      virus.append(((graph[i][j], i, j)))
S, X, Y = map(int, input().split())
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs(s, X, Y):
  q = deque(virus)
  count = 0
  while q:
    if count == s:
      break
    for _ in range(len(q)):
      prev, 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] == 0:
            graph[nx][ny] = graph[x][y]
            q.append((graph[nx][ny], nx, ny))
    count += 1
  return graph[X-1][Y-1]
 
virus.sort()
print(bfs(S, X, Y))
 cs

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

백준 알고리즘 18428: 감시 피하기(Python)  (0) 2020.12.05
백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05
백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05
백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)  (0) 2020.12.04
백준 알고리즘 15686: 치킨 배달 (Python)  (0) 2020.11.30

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

문제

문제 해결을 위한 과정

이 문제의 경우 조건을 보면 8 x 8로 크기가 제한이 되어있는 것을 알 수 있습니다. 또한 3가지의 벽을 세우는 경우 이므로 64가지의 경우에서 순서에 상관없이 3을 뽑는 즉 64C3이기 때문에 완전 탐색으로 해결해야 함을 알 수 있습니다. 따라서 그래프를 입력받을 때 바이러스인 좌표를 저장하는 리스트와 빈칸을 저장하는 리스트를 각각 만든 후 빈칸의 영역에서 combinations을 사용하여 3개의 구역에 벽을 세운 후 BFS를 이용하여 문제를 해결합니다.

문제 해결을 위한 팁

조합을 이용해 3가지 구역에 대해서 벽을 세운 후 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
43
44
45
46
47
48
49
50
51
from itertools import combinations
from collections import deque
import copy
 
N, M = map(int, input().split())
graph = []
blank = []
virus = []
 
for i in range(N):
  graph.append(list(map(int, input().split())))
  for j in range(M):
    if graph[i][j] == 0:
      blank.append((i, j))
    elif graph[i][j] == 2:
      virus.append((i, j))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs():
  testgraph = copy.deepcopy(graph)
  q = deque(virus)
  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 testgraph[nx][ny] == 0:
            testgraph[nx][ny] = 2
            q.append((nx, ny))
 
  count = 0
  for i in range(N):
    for j in range(M):
      if testgraph[i][j] == 0:
        count += 1
  
  return count
 
 
answer = 0
for data in combinations(blank, 3):
  for x, y in data:
    graph[x][y] = 1
  answer = max(answer, bfs())
  for x, y in data:
    graph[x][y] = 0
 
print(answer)
 cs

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

백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05
백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05
백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)  (0) 2020.12.04
백준 알고리즘 15686: 치킨 배달 (Python)  (0) 2020.11.30
백준 알고리즘 3190: 뱀(Python, c++)  (0) 2020.11.29

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

 

18352번: 특정 거리의 도시 찾기

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

문제 

문제 해결을 위한 과정

이 문제의 경우 BFS를 통해서 쉽게 해결할 수 있는 문제였습니다. 정답률은 32퍼센트로 좀 낮은 편인데 난이도에 비해서는 정답률이 조금 낮게 나온 것 같습니다. BFS라는 개념을 정확히 알면 쉬운 문제입니다. 만일 BFS를 잘 모르시겠다면 https://bgspro.tistory.com/15?category=981927

 

BFS 너비 우선탐색 (Python)

BFS란? BFS 즉 Breath-Frist-Search는 영어를 해석한 그대로 넓이를 우선으로 탐색하는 즉 깊이 우선 탐색입니다. 넓이를 우선 탐색한다는 것은 그래프에서 한 노드에서 연결된 다른 노드들을 퍼져가면

bgspro.tistory.com

한번 보고 오시는걸 추천드립니다. 예시의 그림을 보면 노드가 양방향으로 연결이 된 것이 아닌 단방향으로 연결이 되어있는 것을 확인할 수 있습니다.  시작 지점부터 BFS방식을 통해 탐색을 해 나아가면 예시의 그림을 예로 들면 첫 번째로 탐색이 되는 2, 3 그리고 두 번째로 탐색이 되는 4를 통해 몇 번째로 탐색이 되느냐가 시작 지점 노드 1부터 얼마만큼의 거리가 떨어져 있는지를 의미하는 것이라고 보면 되겠습니다. 따라서 몇 번째로 탐색이 되는지 확인을 한 뒤 입력받은 k와 같다면 어떠한 리스트에 추가를 한 뒤 오름차순으로 정렬을 하면 되는 문제였습니다.

소스코드 
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
import sys
from collections import deque
# 입력을 빠르게 하기 위함 이 방식이 아닌 일반 input일 경우 pypy3는 통과하지만 python3로는 통과하지 못함
input = sys.stdin.readline 
 
N, M, K, X = map(int, input().split())
graph = [[] for _ in range(1 + N)]
visited = [False] * (1 + N)
answer = []
 
for i in range(M):
  a, b = map(int, input().split())
  graph[a].append(b)
 
def bfs(graph, x, visited):
  queue = deque([x])
  visited[x] = True
  count = 1
  while queue:
    for _ in range(len(queue)): # 몇번째로 탐색이 되는지 확인하기 위한 for문
      v = queue.popleft()
      for i in graph[v]:
        if not visited[i] and count == K: # 방문하지 않고 K와 ㅏㅌ은 경우
          answer.append(i)
        if not visited[i]: # 방문하지 않은 경우
          visited[i] = True
          queue.append(i)
    count += 1
 
bfs(graph, X, visited)
answer.sort() # 오름차순으로 
 
if len(answer) != 0:
  for data in answer:
    print(data)
else:
  print(-1)
 
 
 cs

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

백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05
백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05
백준 알고리즘 15686: 치킨 배달 (Python)  (0) 2020.11.30
백준 알고리즘 3190: 뱀(Python, c++)  (0) 2020.11.29
백준 알고리즘 1914: 하노이 탑  (0) 2020.11.28

+ Recent posts

티스토리툴바