25.03.20 코딩테스트 대비

BOJ 11660. 구간 합 구하기 5

---

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

 

 

내 코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

board = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(n):
        if i == 0 and j == 0:
            continue
        elif j == 0:
            board[i][j] += board[i-1][-1]
        else:
            board[i][j] += board[i][j-1]

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
    
    answer = 0
    for i in range(x1, x2+1):
        if i == 0:
            if y1 == 0:
                answer += board[i][y2]
            else:
                answer += board[i][y2] - board[i][y1-1]
        else:
            if y1 == 0:
                answer += board[i][y2] - board[i-1][-1]
            else:
                answer += board[i][y2] - board[i][y1 -1]

    print(answer)

누적합을 구해 쉽게 해결할 수 있었다.

 

2차원 배열의 누적합을 미리 계산해놓고 각 구간의 합을 더해 문제를 해결했다.

 

예를 들어 board가 다음과 같다면

[1, 2, 3, 4]

[2, 3, 4, 5]

[3, 4, 5, 6]

[4, 5, 6, 7]

 

다음과 같이 누적합을 구할 수 있다.

[ 1,   3,   6,  10]

[12, 15, 19, 24]

[27, 31, 36, 42]

[46, 51, 57, 64]

 

여기서 (2, 2)에서 (3, 4) 구간의 합을 구하면 다음과 같다.

 

answer = 0

answer += board[2][4] - board[2][1] = 12

answer += board[3][4] - board[3][1] = 12 + 42 - 27 = 27

print(answer) #27

 

 

내 제출

 

처음에 테스트용 print문을 지우지 않고 제출해서 출력 초과가 떴다...

 

 

BOJ 11779. 최소비용 구하기 2

---

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

 

 

 

내 코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    v1, v2, cost = map(int, input().split())
    graph[v1-1].append([v2-1, cost])

start, end = map(int, input().split())

def dijkstra(start):
    distances = [[float('inf'), []] for _ in range(n)]
    distances[start-1] = [0, [start]]
    q = []
    heapq.heappush(q, (0, start-1, [start]))

    while q:
        distance, now, path = heapq.heappop(q)
        if distances[now][0] < distance:
            continue
            
        for next in graph[now]:
            cost = distance + next[1]
            if cost < distances[next[0]][0]:
                distances[next[0]][0] = cost
                distances[next[0]][1] = path + [next[0]+1]
                heapq.heappush(q, (cost, next[0], distances[next[0]][1]))
    return distances

answer = dijkstra(start)[end-1]
print(answer[0])
print(len(answer[1]))
print(*answer[1])

 

다익스트라를 통해 쉽게 해결할 수 있는 문제였다. 

 

단순히 최단 경로의 weight 값을 출력하는 것이 아닌 경로까지 함께 출력해야해서 골드 3이지 않나 싶다.

 

distances에 최단 경로를 업데이트할 때, path도 함께 업데이트 하여 저장하여 쉽게 해결할 수 있었다.

 

 

 

내 제출

처음 제출했을 때, 코드가 너무 더러워 위와 같이 좀 수정했다..

 

 

BOJ 2638. 치즈

---

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

 

 

 

내 코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(n)]

moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def bfs(x, y, visited):
    q = deque([(x, y)])
    visited[x][y] = 1

    while q:
        x, y = q.popleft()
        for move in moves:
            nx = x + move[0]
            ny = y + move[1]

            if 0 <= nx < n and 0 <= ny < m:
                
                if paper[nx][ny] == 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                elif paper[nx][ny] == 1:
                    visited[nx][ny] += 1

answer = 0

while True:
    answer += 1
    visited = [[0] * m for _ in range(n)]
    bfs(0, 0, visited)

    for i in range(n):
        for j in range(m):
            if visited[i][j] >= 2:
                paper[i][j] = 0

    if sum([sum(row) for row in paper]) == 0:
        break

print(answer)

재밌는 bfs 응용 문제였던 것 같다.

 

가장자리 공기를 기준으로 bfs를 돌려 현재 위치의 인접한 위치를 확인한다.

 

인접한 위치가 공기이면 visited[nx][ny]를 1로 설정하고 q에 (nx, ny)를 넣어준다.

인접한 위치가 치즈이면 visited[nx][ny]에 +1을 해준다.

 

bfs를 끝마치고 나와 visited[i][j]가 2 이상이면 0으로 바꿔준다.

 

이러한 과정을 모든 치즈가 없어질 때 까지 반복한다.

 

각 반복에는 answer도 +1씩 해주어 몇 시간이 걸리는지 저장한다.

 

마지막에는 이러한 answer를 반환하여 정답을 맞을 수 있었다.

 

 

내 제출