'알고리즘/백준' 카테고리의 글 목록 (4 Page)

알고리즘/백준

백준 21608번: 상어 초등학교(Python) 2024.04.03
백준 21610번: 마법사 상어와 비바라기(Python) 2024.04.02
백준 1238번: 파티(Python, cpp) 2022.02.27
백준 1753번: 최단경로(Python, cpp) 2022.02.22
백준 12100번: 2048(Python, cpp) 2022.02.21
백준 16236번: 아기상어(Python, cpp) 2022.02.15
백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp) 2022.02.04
백준 알고리즘 11052번: 카드 구매하기(Python) 2022.02.02

백준 21608번: 상어 초등학교(Python)

2024. 4. 3. 13:13

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

21608번: 상어 초등학교

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호

www.acmicpc.net

문제 해결을 위한 과정

구현 유형에 해당하는 문제 입니다. 조건 자체는 복잡할 수 있으나, 조건에 유의하여 소스코드를 작성하면 해결할 수 있었습니다. (저의 경우 possible.append()를 graph[nx][ny] == 0 즉 비어있을 때만 해줘야하는데 실수로 그렇지 않은 경우에도 append할 수 있게 작성하여 여러번 시도하여 해결했습니다.)

소스코드

a = int(input())
n = a * a
graph = [[0] * a for _ in range(a)]
friend = []
happy = [0, 1, 10, 100, 1000]
for _ in range(n):
  friend.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(len(friend)):
  main = friend[i][0]
  bestFriend = friend[i][1:5]
  possible = []
  
  for j in range(a):
    for k in range(a):
      cnt = 0
      emptyCnt = 0
      if graph[j][k] == 0:
        for l in range(4):
          nj = j + dx[l]
          nk = k + dy[l]
          if nj < 0 or nk < 0 or nj >= a or nk >= a:
            continue
          if graph[nj][nk] in bestFriend:
            cnt += 1
          elif graph[nj][nk] == 0:
            emptyCnt += 1
            
        possible.append((cnt, emptyCnt, j, k))
  possible.sort(key=lambda x: (-x[0], -x[1], x[2], x[3]))
  j, k, x, y = possible[0]
  graph[x][y] = main
  
ans = 0
for i in range(a):
  for j in range(a):
    for k in range(len(friend)):
      if graph[i][j] == friend[k][0]:
        bestFriend = friend[k][1:5]
        cnt = 0
        for l in range(4):
          nx = i + dx[l]
          ny = j + dy[l]
          if nx < 0 or ny < 0 or nx >= a or ny >= a:
            continue
          if graph[nx][ny] in bestFriend:
            cnt += 1
        ans += happy[cnt]
print(ans)

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

백준 9663번: N-Queen(Python) (0)	2024.04.06
백준 14891번: 톱니바퀴 (Python) (0)	2024.04.04
백준 21610번: 마법사 상어와 비바라기(Python) (0)	2024.04.02
백준 1238번: 파티(Python, cpp) (0)	2022.02.27
백준 1753번: 최단경로(Python, cpp) (0)	2022.02.22

백준 21610번: 마법사 상어와 비바라기(Python)

2024. 4. 2. 10:40

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

21610번: 마법사 상어와 비바라기

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기

www.acmicpc.net

문제 해결을 위한 과정

구현 유형에 해당하는 문제 이므로 문제에서 주어진 조건을 따라서 차분하게 작성하면 어렵지 않게 풀 수 있는 문제 입니다. 문제의 예시를 보고 한 단계씩 확인하면서 작성하여 크게 어렵지 않게 해결할 수 있었습니다.

소스코드

n, m = map(int, input().split())
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
moves = []
for _ in range(m):
  x, y = map(int, input().split())
  moves.append((x-1, y))
cloud = [(n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)]

def move_cloud(d, s):
  length = len(cloud)
  for i in range(length):
    x, y = cloud[0]
    cloud.pop(0)
    nx = x + dx[d] * s
    ny = y + dy[d] * s
    nx = nx % n
    ny = ny % n
    cloud.append((nx, ny))

for i in range(len(moves)):
  d, s = moves[i]
  move_cloud(d, s)
  for j in range(len(cloud)):
    x, y = cloud[j]
    graph[x][y] += 1
  for j in range(len(cloud)):
    x, y = cloud[j]
    count = 0
    for k in range(1, 8, 2):
      nx = x + dx[k]
      ny = y + dy[k]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if graph[nx][ny] >= 1:
        count += 1
    graph[x][y] += count 
  tempCloud = []
  for a in range(n):
    for b in range(n):
      if graph[a][b] >= 2 and (a, b) not in cloud:
        tempCloud.append((a, b))
  cloud.clear()
  for j in range(len(tempCloud)):
    x, y = tempCloud[j]
    cloud.append((x, y))
    graph[x][y] -= 2

ans = 0
for i in range(n):
  for j in range(n):
    ans += graph[i][j]
print(ans)

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

백준 14891번: 톱니바퀴 (Python) (0)	2024.04.04
백준 21608번: 상어 초등학교(Python) (0)	2024.04.03
백준 1238번: 파티(Python, cpp) (0)	2022.02.27
백준 1753번: 최단경로(Python, cpp) (0)	2022.02.22
백준 12100번: 2048(Python, cpp) (0)	2022.02.21

백준 1238번: 파티(Python, cpp)

2022. 2. 27. 23:44

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

1238번: 파티

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 역방향을 생각해야 하는 것이 가장 중요한 문제였습니다. 예제에서 파티가 열리는 장소가 2번이기 때문에 2를 다익스트라 알고리즘의 start로 넣어주면 2에서 다른 지점으로 가는 최소 거리를 구할 수 있고

역방향 그래프를 생성한 후 역방향의 그래프로 2를 다익스트라 알고리즘의 start로 넣어주면 다른 지점에서 2로 가는 최소 거리를 구할 수 있습니다.

소스코드 - 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
53

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
 
n, m, x = map(int, input().split())
graph = [[] for _ in range(1+n)]
graphR = [[] for _ in range(1+n)]
distance = [INF] * (n+1)
distanceR = [INF] * (n+1)
 
for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graphR[b].append((a, c))
  
def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      continue
    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))
 
def dijkstraR(start):
  q = []
  heapq.heappush(q, (0, start))
  distanceR[start] = 0
  while q:
    dist, now = heapq.heappop(q)
    if distanceR[now] < dist:
      continue
    for i in graphR[now]:
      cost = dist + i[1]
      if cost < distanceR[i[0]]:
        distanceR[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))
        
dijkstra(x)
dijkstraR(x)
 
result = []
for i in range(1, n+1):
  result.append(distance[i] + distanceR[i])
 
result.sort(reverse = True)
print(result[0])

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

#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
 
vector<pair<int, int>> graph[MAX];
vector<pair<int, int>> graphR[MAX];
vector<int> result;
int d[MAX];
int dR[MAX];
int n, m, x;
 
void dijkstra(int start) {
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));
    d[start] = 0;
    while (!pq.empty()) {
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        for (int i = 0; i < graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            if (cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push(make_pair(-cost, graph[now][i].first));
            }
        }
    }
}
 
void dijkstraR(int start) {
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));
    dR[start] = 0;
    while (!pq.empty()) {
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        for (int i = 0; i < graphR[now].size(); i++) {
            int cost = dist + graphR[now][i].second;
            if (cost < dR[graphR[now][i].first]) {
                dR[graphR[now][i].first] = cost;
                pq.push(make_pair(-cost, graphR[now][i].first));
            }
        }
    }
}
 
int main(void) {
    scanf("%d %d %d", &n, &m, &x);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graphR[b].push_back(make_pair(a, c));
    }
 
    int INF = (int)1e9;
    fill(d, d + MAX, INF);
    fill(dR, dR + MAX, INF);
    dijkstra(x);
    dijkstraR(x);
 
    for (int i = 1; i < n+1; i++) {
        result.push_back(d[i] + dR[i]);
    }
    
    sort(result.begin(), result.end(), greater<int>());
    
    cout << result[0] << endl;
    return 0;
}
Colored by Color Scripter

cs

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

백준 21608번: 상어 초등학교(Python) (0)	2024.04.03
백준 21610번: 마법사 상어와 비바라기(Python) (0)	2024.04.02
백준 1753번: 최단경로(Python, cpp) (0)	2022.02.22
백준 12100번: 2048(Python, cpp) (0)	2022.02.21
백준 16236번: 아기상어(Python, cpp) (0)	2022.02.15

백준 1753번: 최단경로(Python, cpp)

2022. 2. 22. 00:39

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

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가

www.acmicpc.net

문제 해결을 위한 과정

다익스트라 알고리즘을 이용하여 해결할 수 있는 문제였습니다. 다익스트라 기본 코드를 정확하게 알고 있다면 매우 쉽게 해결할 수 있었습니다.

소스코드 - 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

import heapq, sys
input = sys.stdin.readline
INF = int(1e9)
 
 
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
 
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
v, e = map(int, input().split())
start = int(input())
graph = [[] for _ in range(v+1)]
distance = [INF] * (v+1)
 
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
 
dijkstra(start)
 
for i in range(1, v+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])
 
Colored by Color Scripter

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

#include <bits/stdc++.h>
#define MAX 20001
#define INF (int)1e9
using namespace std;
vector<pair<int, int> > graph[MAX];
int d[MAX];
int v, e;
 
void dijkstra(int start) {
    priority_queue<pair<int, int> > pq;
    pq.push({ 0, start });
    d[start] = 0;
 
    while (!pq.empty()) {
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if (d[now] < dist)
            continue;
        for (int i = 0; i < (signed)graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            if (cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push({ -cost, graph[now][i].first });
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> v >> e;
    int start;
    cin >> start;
    fill(d, d + MAX, INF);
 
    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }
 
    dijkstra(start);
 
    for (int i = 1; i <= v; i++) {
        if (d[i] == INF) {
            cout << "INF" << "\n";
        }
        else {
            cout << d[i] << "\n";
        }
    }
    return 0;
}
Colored by Color Scripter

cs

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

백준 21610번: 마법사 상어와 비바라기(Python) (0)	2024.04.02
백준 1238번: 파티(Python, cpp) (0)	2022.02.27
백준 12100번: 2048(Python, cpp) (0)	2022.02.21
백준 16236번: 아기상어(Python, cpp) (0)	2022.02.15
백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp) (0)	2022.02.04

백준 12100번: 2048(Python, cpp)

2022. 2. 21. 18:28

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

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 백트레킹 및 dfs 방식으로 해결할 수 있었다. dfs함수를 짜는 건 어렵지 않았지만 이동하는 함수 moveGraph 함수는 작성하기 어려웠다. 다만 차근차근 조건을 따져가며 작성하니 생각보다는 어렵지 않았던 문제였다. https://chldkato.tistory.com/163 이 분의 포스팅을 참조하여 소스코드를 작성하였다. 구현 유형을 조금 더 많이 접하여 친숙해진다면 보다 쉽게 해결할 수 있을것으로 기대된다.

소스코드 - python

import copy

def move(dir): # n e s w
    if dir == 0:
        for j in range(n):
            idx = 0
            for i in range(1, n):
                if graph[i][j] != 0: # if not 0
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[idx][j] == temp:
                        graph[idx][j] *= 2
                        idx += 1
                    elif graph[idx][j] == 0:
                        graph[idx][j] = temp  
                    elif graph[idx][j] != temp:
                        idx += 1
                        graph[idx][j] = temp
                        

    elif dir == 1:
        for i in range(n):
            idx = n-1
            for j in range(n-2, -1, -1):
                if graph[i][j] != 0: # if not 0
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[i][idx] == temp:
                        graph[i][idx] *= 2
                        idx -= 1
                    elif graph[i][idx] == 0:
                        graph[i][idx] = temp
                    elif graph[i][idx] != temp:
                        idx -= 1
                        graph[i][idx] = temp
                        
    
    elif dir == 2: # s
        for j in range(n):
            idx = n-1
            for i in range(n-2, -1, -1):
                if graph[i][j] != 0:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[idx][j] == temp:
                        graph[idx][j] *= 2
                        idx -= 1
                    elif graph[idx][j] == 0:
                        graph[idx][j] = temp
                    elif graph[idx][j] != temp:
                        idx -= 1
                        graph[idx][j] = temp
                        

    elif dir == 3: # w
        for i in range(n):
            idx = 0
            for j in range(1, n):
                if graph[i][j] != 0:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[i][idx] == temp:
                        graph[i][idx] *= 2
                        idx += 1
                    elif graph[i][idx] == 0:
                        graph[i][idx] = temp
                    elif graph[i][idx] != temp:
                        idx += 1
                        graph[i][idx] = temp
                        

def dfs(count):
    global ans, graph
    if count == 5: # 5인 경우
        for i in range(n):
            ans = max(ans, max(graph[i]))
        return

    copyGraph = copy.deepcopy(graph)
    for i in range(4):
        move(i)
        dfs(count + 1)
        graph = copy.deepcopy(copyGraph)
        

n = int(input())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
ans = 0
dfs(0)
print(ans)

소스코드 - c++

#include <bits/stdc++.h>
#define MAX 21	
using namespace std;

int n;
int graph[MAX][MAX];
int ans;

void moveGraph(int dir) { // N, E, S, W
	if (dir == 0) {
		for (int j = 0; j < n; j++) {
			int idx = 0;
			for (int i = 1; i < n; i++) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[idx][j] == temp) {
						graph[idx][j] *= 2;
						idx += 1;
					}
					else if (graph[idx][j] == 0)
						graph[idx][j] = temp;
					else {
						idx += 1;
						graph[idx][j] = temp;
					}
				}
			}
		}
	}

	else if (dir == 1) {
		for (int i = 0; i < n; i++) {
			int idx = n-1;
			for (int j = n-2; j > -1; j--) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[i][idx] == temp) {
						graph[i][idx] *= 2;
						idx -= 1;
					}
					else if (graph[i][idx] == 0)
						graph[i][idx] = temp;
					else {
						idx -= 1;
						graph[i][idx] = temp;
					}
				}
			}
		}
	}

	else if (dir == 2) {
		for (int j = 0; j < n; j++) {
			int idx = n-1;
			for (int i = n-2; i > -1; i--) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[idx][j] == temp) {
						graph[idx][j] *= 2;
						idx -= 1;
					}
					else if (graph[idx][j] == 0)
						graph[idx][j] = temp;
					else {
						idx -= 1;
						graph[idx][j] = temp;
					}
				}
			}
		}
	}

	else {
		for (int i = 0; i < n; i++) {
			int idx = 0;
			for (int j = 1; j < n; j++) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[i][idx] == temp) {
						graph[i][idx] *= 2;
						idx += 1;
					}
					else if (graph[i][idx] == 0)
						graph[i][idx] = temp;
					else {
						idx += 1;
						graph[i][idx] = temp;
					}
				}
			}
		}
	}
}

void dfs(int count) {
	if (count == 5) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				ans = max(ans, graph[i][j]);
			}
		}
		return;
	}

	int copyGraph[MAX][MAX] = { 0, };
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			copyGraph[i][j] = graph[i][j];
		}
	}

	for (int k = 0; k < 4; k++) {
		moveGraph(k);
		dfs(count + 1);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				graph[i][j] = copyGraph[i][j];
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
		}
	}
	dfs(0);
	cout << ans;
	return 0;
}

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

백준 1238번: 파티(Python, cpp) (0)	2022.02.27
백준 1753번: 최단경로(Python, cpp) (0)	2022.02.22
백준 16236번: 아기상어(Python, cpp) (0)	2022.02.15
백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp) (0)	2022.02.04
백준 알고리즘 11052번: 카드 구매하기(Python) (0)	2022.02.02

백준 16236번: 아기상어(Python, cpp)

2022. 2. 15. 22:19

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

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

문제 해결을 위한 과정

구현 유형에 해당하는 문제 이므로 문제에서 주어진 조건을 따라서 차분하게 작성하면 쉽게 해결할 수 있는 문제 입니다. bfs를 통해 이동할 수 있는 구역을 탐색한 후 먹을 수 있는 물고기들을 배열에 담아 정렬 후 가장 첫번째에 있는 물고기를 먹으면 되는 문제 입니다.

소스코드 - python

from collections import deque

def bfs(x, y, size, visited):
  q = deque()
  q.append((x, y))
  count = 0
  visited[x][y] = 1
  while q:
    for _ in range(len(q)):
      x, y = q.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
          continue
        if graph[nx][ny] <= size and visited[nx][ny] == 0:
          q.append((nx, ny))
          visited[nx][ny] = 1
          if 0 < graph[nx][ny] < size:
            eatable.append((count+1, nx, ny))
    count += 1

n = int(input())
graph = []
x = 0
y = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
size = 2 
eatable = []

for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(n):
    if graph[i][j] == 9:
      x, y = i, j
      graph[i][j] = 0

timeInfo = 0
eatCount = 0
while True:
  visited = [[0] * n for _ in range(n)]
  bfs(x, y, size, visited)
  if len(eatable) == 0:
    print(timeInfo)
    break
  eatable.sort()
  dist, xPos, yPos = eatable[0]
  eatable = []
  x, y = xPos, yPos
  graph[x][y] = 0
  timeInfo += dist
  eatCount += 1
  if eatCount == size:
    size += 1
    eatCount = 0

소스코드 - c++

#include <bits/stdc++.h>

using namespace std;

int graph[20][20];
int visited[20][20];
int n;
int sizeOfShark;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
vector<tuple<int, int, int>> eatable; // 거리, x좌표, y좌표

void bfs(int xPos, int yPos) {
	queue<pair<int, int>> q;
	q.push(make_pair(xPos, yPos));
	visited[xPos][yPos] = 1;
	int num = 0;
	int distance = 0;

	while (!q.empty()) {
		num = q.size();
		for (int i = 0; i < num; i++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
					continue;
				}
				if (graph[nx][ny] <= sizeOfShark && visited[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					visited[nx][ny] = 1;
					if (0 < graph[nx][ny] && graph[nx][ny] < sizeOfShark) {
						eatable.push_back(make_tuple(distance + 1, nx, ny));
					}
				}
			}
		}
		distance += 1;
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	int x = 0, y = 0; // 상어 좌표
	sizeOfShark = 2; // 초기 상어 크기

	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j]; // 그래프 입력 받기
			if (graph[i][j] == 9) { // 상어 위치인 경우
				x = i;
				y = j;
				graph[i][j] = 0;
			}
		}
	}

	int timeInfo = 0;
	int eatCount = 0;

	while (true) {
		fill(&visited[0][0], &visited[19][20], 0);
		bfs(x, y);
		if (eatable.size() == 0) {
			cout << timeInfo;
			break;
		}
		sort(eatable.begin(), eatable.end());
		int dist = get<0>(eatable[0]);
		int xPos = get<1>(eatable[0]);
		int yPos = get<2>(eatable[0]);
		eatable.clear();
		x = xPos;
		y = yPos;
		graph[x][y] = 0;
		timeInfo += dist;
		eatCount += 1;
		if (eatCount == sizeOfShark) {
			sizeOfShark += 1;
			eatCount = 0;
		}
	}
	return 0;
}

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

백준 1753번: 최단경로(Python, cpp) (0)	2022.02.22
백준 12100번: 2048(Python, cpp) (0)	2022.02.21
백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp) (0)	2022.02.04
백준 알고리즘 11052번: 카드 구매하기(Python) (0)	2022.02.02
백준 알고리즘 9461번: 파도반 수열(Python) (0)	2022.01.31

백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp)

2022. 2. 4. 17:14

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

1697번: 숨바꼭질

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

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 일반적인 이차원 배열 형태에서의 bfs와 다른 형태의 문제이지만 원리는 똑같은 문제였습니다.

4방향으로 dx, dy로 방문하는 배열을 3가지 움직임(-1, 1, 좌표*2)를 방문하는 형태로 해결하면 쉽게 해결할 수 있었습니다. 다만, 신경써야할 부분은 시작하자마자 좌표가 같은 경우가 있을 수 있으므로 이것에 대한 예외처리를 해주시면 쉽게 해결할 수 있습니다.

소스코드 - python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

from collections import deque
n,k=map(int,input().split())
visited=[0]*100001
q=deque()
q.append(n)
count=0
visited[n]=1
while q:
  x=q.popleft()
  if x==k:
    break
  for next in x-1,x+1,x*2:
    if next < 0 or next >= 100001:
      continue
    if not visited[next]:
      q.append(next)
      visited[next]=visited[x] + 1
print(visited[k]-1)

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

#include <bits/stdc++.h>
#define MAX 100001
 
using namespace std;
 
int graph[MAX];
int moves[] = { -1, 1, 2 };
 
void bfs(int n, int k) {
    int count = 0;
    queue<int> q;
    q.push(n);
    graph[n] = 1;
    if (n == k) {
        printf("%d", count);
        return;
    }
 
    while (!q.empty()) {
        int len = q.size();
        for (int i = 0; i < len; i++) {
            int x = q.front();
            q.pop();
            for (int i = 0; i < 3; i++) {
                int nx;
                if (i == 2)
                    nx = x * moves[2];
                else
                    nx = x + moves[i];
                if (nx < 0 || nx >= MAX)
                    continue;
                if (graph[nx] == 0) {
                    q.push(nx);
                    graph[nx] = 1;
                }
                if (nx == k) {
                    printf("%d", count+1);
                    return;
                }
            }
        }
        count += 1;
    }
}
 
int main(void) {
    int n, k;
    scanf("%d %d", &n, &k);
 
    bfs(n, k);
    return 0;
}
Colored by Color Scripter

cs

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

백준 12100번: 2048(Python, cpp) (0)	2022.02.21
백준 16236번: 아기상어(Python, cpp) (0)	2022.02.15
백준 알고리즘 11052번: 카드 구매하기(Python) (0)	2022.02.02
백준 알고리즘 9461번: 파도반 수열(Python) (0)	2022.01.31
백준 알고리즘 2193번: 이친수(Python) (0)	2022.01.31

백준 알고리즘 11052번: 카드 구매하기(Python)

2022. 2. 2. 16:04

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

11052번: 카드 구매하기

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 dp 문제로써 점화식을 세워 i번째에 올 max값을 구하면 해결할 수 있는 문제입니다. 소스코드를 작성하면 다음과 같습니다.

소스코드 - python

1
2
3
4
5
6
7
8
9
10
11

n = int(input())
data = list(map(int, input().split()))
dp = [0] * n
dp[0] = data[0]
 
for i in range(1, n):
  dp[i] = max(data[i], dp[i-1] + dp[0])
  for j in range(i//2+1):
    dp[i] = max(dp[i], dp[j] + dp[i-j-1])
 
print(dp[n-1]

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

#define MAX 1001
#include <bits/stdc++.h>
 
using namespace std;
 
int main(void) {
    int n, dp[MAX], data[MAX];
    scanf("%d", &n);
 
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &data[i]);
    }
    dp[0] = data[0];
 
    for (int i = 1; i < n; i++) {
        dp[i] = max(data[i], dp[i - 1] + dp[0]);
        for (int j = 0; j < i / 2 + 1; j++) {
            dp[i] = max(dp[i], dp[j] + dp[i - j - 1]);
        }
     }
 
    printf("%d", dp[n - 1]);
    return 0;
}
Colored by Color Scripter

cs

 

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

백준 16236번: 아기상어(Python, cpp) (0)	2022.02.15
백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp) (0)	2022.02.04
백준 알고리즘 9461번: 파도반 수열(Python) (0)	2022.01.31
백준 알고리즘 2193번: 이친수(Python) (0)	2022.01.31
백준 알고리즘 11057번: 오르막 수(Python) (0)	2022.01.29

PREV 1 2 3 4 5 6 7 ···14 NEXT

방구석프로의 이야기