oneway's history

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

BFS로 최단거리 찾기 문제인데, 3차원인 경우이다.

따라서 배열을 3중으로 사용하였다.

그것만 헷갈리지 않으면 전혀 어렵지 않은 문제.

정답 풀이:

import sys
from collections import deque
input = sys.stdin.readline

dh = [-1, 1, 0, 0, 0, 0]
dr = [0, 0, -1, 1, 0, 0]
dc = [0, 0, 0, 0, -1, 1]

while True:
    h, r, c = map(int, input().split(" "))
    if h == 0 and r == 0 and c == 0:
        break

    sh, sr, sc = -1, -1, -1
    eh, er, ec = -1, -1, -1

    graph = []
    for H in range(h):
        tgraph = []
        for R in range(r):
            tlist = list(map(str, input().rstrip()))

            for C in range(c):
                if tlist[C] == 'S':
                    sh, sr, sc = H, R, C
                elif tlist[C] == 'E':
                    eh, er, ec = H, R, C

            tgraph.append(tlist)
        graph.append(tgraph)
        input()

    queue = deque()
    visited = [[[False for _ in range(c)] for _ in range(r)] for _ in range(h)]
    queue.append((sh, sr, sc, 0))
    visited[sh][sr][sc] = True

    escapeTime = -1
    while queue:
        H, R, C, time = queue.popleft()

        if H == eh and R == er and C == ec:
            escapeTime = time
            break

        for i in range(6):
            nh = H + dh[i]
            nr = R + dr[i]
            nc = C + dc[i]

            if 0 <= nh < h and 0 <= nr < r and 0 <= nc < c and graph[nh][nr][nc] != '#' and visited[nh][nr][nc] == False:
                queue.append((nh, nr, nc, time+1))
                visited[nh][nr][nc] = True

    if escapeTime == -1:
        print("Trapped!")
    else:
        print("Escaped in {} minute(s).".format(escapeTime))

결과

오타 하나 나서 틀렸었다 ^^..

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

최단거리를 구하는 BFS와 시뮬레이션이 합쳐진 문제다.

불을 먼저 퍼트리고, 지훈이 그 다음 이동하도록 하였다.

그 반대로 하려면 좀 까다로웠기 때문이다.

불과 지훈이 한 번에 한 칸씩만 퍼져야 했기 때문에

queue에서 popleft 할 때 fcnt, jcnt 만큼만 꺼내서 퍼지도록 했다.

정답 소스코드

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split(" "))
graph = []
for i in range(R):
    s = input().rstrip()
    graph.append(list(s))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

fqueue = deque()
jqueue = deque()

fcnt = 0
jcnt = 0
for r in range(R):
    for c in range(C):
        if graph[r][c] == 'F':
            fqueue.append((r, c))
            fcnt += 1
        if graph[r][c] == 'J':
            jqueue.append((r, c))
            jcnt += 1


time = 0
escaped = False
while True:
    time += 1
    # 불번짐 먼저 시작
    ftmp = 0
    for f in range(fcnt):
        r, c = fqueue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < R and 0 <= nc < C:
                if graph[nr][nc] == 'J' or graph[nr][nc] == '.':
                    fqueue.append((nr, nc))
                    ftmp += 1
                    graph[nr][nc] = 'F'
    fcnt = ftmp

    # 지훈이 이동
    jtmp = 0
    died = True
    for j in range(jcnt):
        r, c = jqueue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < R and 0 <= nc < C:
                if graph[nr][nc] == '.':
                    died = False
                    jqueue.append((nr, nc))
                    jtmp += 1
                    graph[nr][nc] = 'J'
            else:
                # 탈출 성공
                escaped = True
    jcnt = jtmp

    if escaped == True:
        print(time)
        break
    if died == True:
        print("IMPOSSIBLE")
        break

# 시뮬레이션과 BFS가 합쳐진 문제
# 반례를 찾느라 정말 많이 틀렸다..

결과

F가 하나도 없을 수 있다는 점을 간과해서 몇 번 틀렸고

jcnt를 사용하지 않고 단 1번만 popleft 해서 이상하게 퍼져서 몇 번 더 틀렸었다.

출력 초과는 디버깅용 print 삭제 안하고 제출했다가 틀린 것..

504ms -> 476ms 줄인 건 visited 배열을 쓰려고 선언만 해놓은거 안써도 풀리길래 삭제했더니 줄었다.

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

그래프 문제인데, N이 50밖에 안되고

진실을 아는 사람은 2로, 모르는 사람은 1로 체크하여

인접행렬 방식을 사용하면 더 편리할 것 같아서

그런 방식으로 코딩을 해봤는데

인접행렬을 약간 오랜만에 다뤄봐서 그런지 버벅였다.

나열된 파티 순서와는 관계 없이,

진실을 아는 사람이 포함된 경우는 거짓말을 할 수 없다는 것을 염두해야함.

정답 코드

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split(" "))  # 사람 수(1부터 시작) , 파티 수

graph = [[0 for i in range(N+1)] for i in range(N+1)]
know = list(map(int, input().split(" ")))[1:]
for k in know:
    for n in know:
        graph[k][n] = 2

queue = deque()
rememberParties = []
for m in range(M):
    partyMember = list(map(int, input().split(" ")))[1:]
    rememberParties.append(partyMember)
    isKnowHere = False
    for p in partyMember:
        if graph[p][p] == 2:
            isKnowHere = True
            break

    if isKnowHere == True:
        # BFS로 2로 싹 변경
        visited = [False for i in range(N+1)]
        for p in partyMember:
            queue.append(p)
            visited[p] = True
            while queue:
                cur = queue.popleft()
                for idx in range(1, N+1):
                    if graph[cur][idx] != 0:
                        graph[cur][idx] = 2
                        if visited[idx] == False:
                            queue.append(idx)
                            visited[idx] = True

        # 2중for로 2로 싹 연결
        for p in partyMember:
            for j in partyMember:
                graph[p][j] = 2

    else:
        # 2중for로 1로 싹 연결
        for p in partyMember:
            for j in partyMember:
                graph[p][j] = 1

answer = 0
for rem in rememberParties:
    canLie = True
    for r in rem:
        if graph[r][r] == 2:
            canLie = False
            break
    if canLie == True:
        answer += 1
print(answer)

# N이 50개라 인접행렬 방식을 사용.
# 진실을 아는 사람을 탐색할 때 BFS 사용
# 순서와 관계없이 진실을 아는 사람과 파티에 있었던 경우도 거짓말을 하지 못하는 것을 고려해야함.
# 아니 그러면 지민이는 몸이 1개인데 많은 파티에 동시에 참석한다는거야 뭐야
# 아무튼 그래서 모든 파티에 대해 진실을 아는 사람이 있었는지 확인하고, 진실을 아는 사람을 알아낸 뒤 다시 한 번 파티에 대입해서 answer 구함

결과

코드가 길다보니 푸는데 좀 시간이 걸렸는데

풀고나서 정답자 코드를 보니까 정말 짧게 잘 풀었더라..

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

구현 카테고리로 검색했는데

이건 그냥 완전탐색 문제 아닌가?

일단은 풀었다.

치킨집이 최대 M개까지 있을 수 있다고 했으니까,

1부터 M까지 치킨집의 위치를 조합(combination)으로 내놓은다음

거기에다 모든 집의 위치와 일일히 치킨거리를 구하고

도시의 치킨거리를 최솟값으로 갱신했다.

itertools의 combination을 오랜만에 사용해볼 수 있는 문제였다.

정답 소스코드

import sys
import itertools
input = sys.stdin.readline
N, M = map(int, input().split(" "))
graph = []
for i in range(N):
    graph.append(list(map(int, input().split(" "))))
home = []
chicken = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            home.append([i, j])
        if graph[i][j] == 2:
            chicken.append([i, j])

answer = sys.maxsize
# 1부터 탐색
for m in range(1, M+1):
    # 조합 이용 (중복 X)
    for chi in itertools.combinations(chicken, m):
        tmp = 0
        # 모든 집에 대해서 일단 탐색 후, 최솟값으로 갱신
        for h in home:
            chilen = sys.maxsize
            for i in range(m):
                chilen = min(chilen, abs(h[0]-chi[i][0]) + abs(h[1]-chi[i][1]))
            tmp += chilen
        answer = min(answer, tmp)

print(answer)

# 완전탐색, 조합

결과

ps.

최근에 삼성SW역량테스트를 보고왔는데,

거기는 아예 외부 라이브러리 사용을 금지했었다.

조합이나 순열같은 알고리즘은 매번 itertools 라이브러리의 힘을 빌리고있는데,

자력으로 풀 수 있도록 공부를 해놓는게 좋을 것 같다.

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

시간초과로 못풀었던 문제였는데, 이제는 풀 수 있을까 해서 다시 도전해봤다.

그래프이론, 구현이 동시에 들어간 문제이다.

시간을 단축시키기 위해 모든 맵을 돌면서 섬의 개수를 세는 동시에,

rlist 라는 배열에 바로 줄여야할 값을 추가해나갔다.

(rlist에 기억해놓는 방식이 아닌, 바로 줄여버리면 바다가 아닌데, 바다로 착각해서 오류난다)

섬의 개수를 셀 때는 BFS를 사용했다.

그리고 한바퀴 다돌면 rlist에 기억해놓은 내용으로

graph의 값을 줄였다.

다 풀었다고 생각해서 제출했지만

빙하가 다 녹아서 사라질때까지 섬이 2개 이상으로 나눠지지 않는 예외처리를 잊어먹어서

1회 틀렸다 ㅠ 역시 문제는 꼼꼼히 읽자.

정답 소스코드

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split(" "))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
graph = []
for i in range(R):
    graph.append(list(map(int, input().split(" "))))

answer = 0
queue = deque()
while True:
    visited = [[False for i in range(C)] for i in range(R)]
    islandCnt = 0
    rlist = []
    for r in range(1, R):
        for c in range(1, C):
            if graph[r][c] != 0 and visited[r][c] == False:
                visited[r][c] = True
                queue.append((r, c))
                islandCnt += 1
                while queue:
                    rr, cc = queue.popleft()
                    zeroCnt = 0
                    for i in range(4):
                        nr = rr + dr[i]
                        nc = cc + dc[i]
                        if graph[nr][nc] == 0:
                            zeroCnt += 1
                        if graph[nr][nc] != 0 and visited[nr][nc] == False:
                            queue.append((nr, nc))
                            visited[nr][nc] = True
                    rlist.append((rr, cc, zeroCnt))

    # 만약 빙하 개수가 2개 이상이다?
    if islandCnt >= 2:
        print(answer)
        break

    # 만약 빙하가 다 녹아서 사라졌는데 빙하 개수가 2개를 넘은적이 없다?
    if len(rlist) == 0:
        print(0)
        break

    # 빙하 녹이기
    for rval in rlist:
        r, c, cnt = rval[0], rval[1], rval[2]
        graph[r][c] -= cnt
        if graph[r][c] < 0:
            graph[r][c] = 0

    answer += 1

결과

예전엔 자바로 알고리즘을 풀곤 했었다..

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

Knapsack 문제라고도 불리는 배낭문제다.

알고리즘을 처음 공부할 때 도대체 어떻게 푸는건지 3시간을 고민해도 못풀었던 문제인데

DP를 이용한 풀이를 공부한 뒤로 풀 수 있게 됐다.

예전에 비슷한 문제를 풀어본적이 있는데, 복습겸 한 번 더 풀어봤다.

지금 생각해도 DP는 경이롭다.. 

DP로 푼 코드(정답)

import sys
input = sys.stdin.readline

N, K = map(int, input().split(" "))
DP = [[0 for i in range(K+1)] for i in range(N+1)]
graph = [[0, 0] for i in range(N+1)]
for i in range(1, N+1):
    graph[i][0], graph[i][1] = map(int, input().split(" "))

# N은 100까지, K는 100,000까지, 총 10,000,000(1초) 필요
for n in range(1, N+1):
    for k in range(1, K+1):
        weight, value = graph[n][0], graph[n][1]
        # 탐색하려는 무게에 못미친경우 이전 무게를 그대로 가져옴
        if k < weight:
            DP[n][k] = DP[n-1][k]
        # 무게 범위 내일 경우
        else:
            # 현재 무게랑 현재 무게만큼 뺐을 때의 이전 값을 더한것과, 이전 값과 비교해서 큰거로 누적
            DP[n][k] = max(DP[n-1][k-weight]+value, DP[n-1][k])

print(DP[N][K])

백트랙킹으로 풀었다가 시간초과난 코드(오답)

# import sys
# input = sys.stdin.readline

# N, K = map(int, input().split(" "))
# graph = [[0, 0] for i in range(N)]
# for i in range(N):
#     graph[i][0], graph[i][1] = map(int, input().split(" "))

# answer = 0
# idx = 0


# def getMaxVal(idx, accw, accv):
#     if accw > K:
#         return

#     global answer
#     if idx == N:
#         answer = accv if answer < accv else answer
#         return

#     w, v = graph[idx][0], graph[idx][1]

#     getMaxVal(idx+1, accw+w, accv+v)
#     getMaxVal(idx+1, accw, accv)


# for i in range(N):
#     getMaxVal(i, 0, 0)  # idx, accweight, accval
# print(answer)

# 백트랙킹 했다가 시간초과 남.

결과

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

거쳐가는 노드의 최소값 구하는거라 다익스트라 쓰는 줄 알았는데
T가 40000번 돌아야해서 매번 최소거리를 구하는게 비효율적임을 너무 늦게 깨우쳤다.

(어딘가에서 무한루프가 도는건가? 싶어서 계속 val값을 깨작깨작 수정하고있었다.)

한 번에 모든 노드->노드 로 가는 최소거리를 구해서

단순히 2차원 배열에서 결과값만 던져주면 되는 플로이드-워셜 알고리즘이 정답이었다.

정답코드

import sys
input = sys.stdin.readline
N, M, T = map(int, input().split(" "))
INF = sys.maxsize
graph = [[INF for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    a, b, val = map(int, input().split(" "))
    graph[a][b] = val
for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            bigger = graph[i][k] if graph[i][k] > graph[k][j] else graph[k][j]
            graph[i][j] = bigger if graph[i][j] > bigger else graph[i][j]

for tc in range(T):
    a, b = map(int, input().split(" "))
    if graph[a][b] != INF:
        print(graph[a][b])
    else:
        print(-1)

틀린코드(다익스트라 써서 시간초과 난 코드)

import heapq
input = sys.stdin.readline
N, M, T = map(int, input().split(" "))
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b, val = map(int, input().split(" "))
    graph[a].append((b, val))
INF = sys.maxsize
for tc in range(T):
    start, end = map(int, input().split(" "))
    distance = [INF for i in range(N+1)]
    heap = []
    heapq.heappush(heap, start)
    distance[start] = 0
    while heap:
        fr = heapq.heappop(heap)
        for g in graph[fr]:
            to, toval = g[0], g[1]
            biggerVal = distance[fr] if distance[fr] > toval else toval
            if distance[to] > biggerVal:
                distance[to] = biggerVal
                heapq.heappush(heap, to)
    print(distance[end] if distance[end] != INF else -1)

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

문제를 딱 읽어보니 최소 루트를 구하는 다익스트라 문제같았다.

그래서 다익스트라를 사용해서 풀었더니 통과됐다.

import sys
import heapq
input = sys.stdin.readline

N, M = map(int, input().split(" "))
graph = [[] for i in range(N+1)]
INF = sys.maxsize
distance = [INF for i in range(N+1)]
for i in range(M):
    a, b, val = map(int, input().split(" "))
    graph[a].append((b, val))
    graph[b].append((a, val))
finalA, finalB = map(int, input().split(" "))
distance[finalA] = 0

heap = []
for i in graph[finalA]:
    to, val = i[0], i[1]
    heapq.heappush(heap, (to, val))
    distance[to] = val

while heap:
    fr, val = heapq.heappop(heap)
    for j in graph[fr]:
        to, toval = j[0], j[1]
        newVal = val + toval
        if distance[to] > newVal:
            distance[to] = newVal
            heapq.heappush(heap, (to, newVal))

print(distance[finalB])

# 다익스트라

while문을 for문 안에 넣었더니 한 번 틀렸다.

굳이 안넣어도 되기때문에 for문 바깥으로 뺐더니 통과됐다.