[TIL] 5주차 - (5) : 스터디 문제 리뷰

오늘은 코알라 스터디 두번째 주간 문제를 풀었다.

 

난이도가 평이할 줄 알았는데 너무 어려워서 가장 쉬웠던 1문제 밖에 못맞추고 나머지 두개는 방향을 잘못 잡아서 풀지 못했다.

 

스터디 끝나고 어려운 나머지 두문제에 대해 토론했고,

 

토론한 내용을 토대로 다시 시도해서 푼 문제에 대해 리뷰하겠다.

 

---

 

BaekJun - #10159 : 저울 (플로이드 워셜)

 

출처 : https://www.acmicpc.net/problem/10159 

10159번: 저울

 

이 문제는 무게가 더 무거운 물건을 방향성 그래프에 저장한 뒤,

 

각 물건 별로 무게 비교가 불가능한 다른 물건이 몇개 존재하는지 출력하는 문제이다.

 

처음에 이 문제를 보고 플로이드 워셜을 바로 떠올리기는 했지만

 

평범한 플로이드 워셜은 a->b , b-> c 의 연결관계를 이어준다기 보단,

 

더 작은 값으로 초기화해주는 개념으로 이해하고 있었어서 적용하기가 쉽지 않았다.

 

그리고 항상 헤깔리는게 3중 for문 변수들과 워셜 로직 순서가 어떻게 되는지 이다.

 

 

 

 

처음 코드는 다음과 같다.

 

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

map_list = [[0 for _ in range(n+1)] for _ in range(n+1)]
ans = [[0,0] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,sys.stdin.readline().split())
    map_list[b][a] = 1
    ans[a][0] += 1
    ans[b][1] += 1

for i in range(1,n+1):
    for j in range(1,n+1):
        if j == i or map_list[i][j]:
            continue
        for k in range(1,n+1):
            if k ==j or k == i:
                continue
            if map_list[i][k] and map_list[k][j]:
                map_list[i][j] = 1
                ans[j][0] += 1
                ans[i][1] += 1
                
for i in range(1,n+1):
    count = 0
    for j in range(2):
        count += ans[i][j]
    print(n-1-count)

 

처음엔 머리속의 로직을 필기해서 그림으로 좀 작동방식을 눈으로 본 후 코드를 짜 나갔다.

 

한쪽 방향으로만 방향성이 있으니, 플로이드 워셜 3 for문 로직을 돌때,

 

더 작은 노드에 무게 비교가 가능한 물건을 탐색했다는 개념으로 +1을 하고

 

더 큰 노드에도 +1을 했다.

 

하지만 이 로직은 아예 틀린 로직이었는데 나중에 알게 되었지만

 

해당 문제는 워셜 로직의 for문 변수의 순서이기도 했고, 중복된 경우를 계산한 문제도 있었다.

 

 

해당 로직을 결국 풀어낸 마지막 코드를 보자.

 

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

map_list = [[0 for _ in range(n+1)] for _ in range(n+1)]
ans = [n-1 for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,sys.stdin.readline().split())
    map_list[a][b] = 1

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if map_list[i][k] == 1 and map_list[k][j] == 1:
                map_list[i][j] = 1

for i in range(1,n+1):
    for j in range(1,n+1):
        if map_list[i][j] == 1:
            ans[i] -= 1
            ans[j] -= 1 
            
                
for i in range(1,n+1):
    count = ans[i]
    print(count)

 

스터디 동료가 제안했던 이 방식은 내가 생각한 방식에서 살짝만 간단히 생각하면 되는 로직이었다.

 

그리고 문제 풀이 과정 중 플로이드 워셜 3중 for문이 디버깅 해보니까 제대로 모든 경우가 체킹되지 않았다.

 

그래서 해당 문제를 디버깅한 뒤 이 코드처럼 for문 변수 위치를 수정했다. (k -> i -> j)

 

그리고 두번째 2중 for문은 플로이드 워셜 로직을 수행한 map 2중 리스트를 탐색하며 행과 열의 번호 인덱스에 정보 값을 -1한다.

 

-1하는 이유는 해당 값과 비교할 수 없는 물건의 수가 하나 줄었다는 의미이다.

 

 

이렇게 저울 문제는 플로이드 워셜 로직을 수정하여 해결할 수 있었다.

 

 

BaekJun - #2206 : 벽부수고 이동하기 (BFS)

 

출처 : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

이 문제는 쉬워보이는데 진짜 어렵다.

 

애초에 처음보는 방식을 사용해야 풀리는 문제였다.

 

문제를 분석해보자.

 

 

2차원의 0과 1의 값을 가진 영역이 주어지는데, 시작 지점(0,0)과 끝 지점(n,n)은 고정되어있다.

 

시작지점으로부터 끝지점까지 가는 최단 거리를 구하는 전형적인 BFS 문제이다.

 

근데 문제는 조건이 하나 추가된다. 바로 벽을 1회성으로 부술 수 있다는 것.

 

그래서 모든 방향성에 벽을 부술 수 있는지에 대한 여부(punch변수가 1이면 부술 수 있는 기회가 남은 상황)를 queue 값에 저장하며 BFS while 문을 돌렸다.

 

그리고 그 값에 따라 if문을 나눴고, 평소와 똑같이 visited 2차원 배열을 사용해서 중복을 방지했다.

 

그 코드가 다음과 같다.

 

import sys
from collections import deque
sys.setrecursionlimit(10**8)

n , m = map(int,sys.stdin.readline().split())
mapList = []
for _ in range(n):
    mapList.append(list(map(int,sys.stdin.readline().strip())))

visited = [[False for _ in range(m)] for _ in range(n)]

def bfs(i,j):
    global n,m
    queue = deque()
    hasPunch = True
    count = 1
    queue.append((i,j,True,count))
    while queue:
        i,j,punch,count = queue.popleft()
        if i == n-1 and j == m-1:
            return count
        visited[i][j] = True
        for di,dj in (0,1), (1,0) , (0,-1) , (-1,0):
            if n-1>=i+di>=0 and m-1>=j+dj>=0:
                if not visited[i+di][j+dj]:
                    if punch and mapList[i+di][j+dj]:
                        queue.append((i+di,j+dj,not punch,count+1))
                    elif not mapList[i+di][j+dj]:
                        queue.append((i+di,j+dj,punch,count+1))
    return -1
                        
print(bfs(0,0))

 

위 코드는 애초에 문제를 접근할 때 처음 제출한 코드여서 다른 부수적인 로직 문제도 있다.

(BFS는 append할때 방문을 해줘야 중복이 방지됨 , 이때는 돌아오는 상황과 바로 도착하는 상황이 벽 때문에 다른 경우일 수 있으니 도착했을 때 True로 변경하는 로직을 해결해 보려고 함.)

 

근데 가장 큰 문제는 다음과 같은 상황을 고려하지 않은 로직 자체의 문제이다.

 

 

만약 이상황에서는 먼저 도달하는 오른쪽 1의 벽을 뛰어 넘어 i=0,j=2 의 0 지역으로 이동할 것이다.

 

그리고 그 지역을 True로 바꾸게 되면, 이 경우는 도달할 수 없는 map이 되어버린다.

 

그래서 이 문제를 해결할 방법은 바로 visited를 펀치를 사용한 경우와 사용하지 않은 경우로 나눠서 방문해주어야 한다는 것이다.

 

그 방법은 바로 visited를 3차원으로 선언하는 것이다.

 

그 방법에 대한 코드는 다음과 같다.

 

import sys
from collections import deque
sys.setrecursionlimit(10**8)

n , m = map(int,sys.stdin.readline().split())
mapList = []
for _ in range(n):
    mapList.append(list(map(int,sys.stdin.readline().strip())))

visited = [[[False for _ in range(2)] for _ in range(m)]for _ in range(n)]

def bfs(i,j):
    global n,m
    queue = deque()
    count = 1
    queue.append((i,j,1,count))
    while queue:
        i,j,punch,count = queue.popleft()
        if mapList[i][j] == 1:
            punch = 0
        if i == n-1 and j == m-1:
            return count
        for di,dj in (0,1), (1,0) , (0,-1) , (-1,0):
            if n-1>=i+di>=0 and m-1>=j+dj>=0:
                
                if mapList[i+di][j+dj] == 1 and punch == 1:
                    if not visited[i+di][j+dj][0]:
                        queue.append((i+di,j+dj,0,count+1))
                        visited[i+di][j+dj][0] == True
                elif mapList[i+di][j+dj] == 1 and punch == 0:
                    continue
                else:
                    if not visited[i+di][j+dj][punch]:
                        queue.append((i+di,j+dj,punch,count+1))
                        visited[i+di][j+dj][punch] = True
    return -1
                        
print(bfs(0,0))

 

visited[n][m][2] 로 선언하여 1차원의 0번째 인덱스에는 펀치를 소모했을 때의 방문 여부, 1번째 인덱스에는 펀치를 소모하지 않았을 때의 방문여부로 나누었다.

 

이 방식을 통해서 문제를 해결할 수 있었고, 이후 메모리 초과의 문제가 발생하여 queue에 불필요한 경로가 추가됬다는 걸 깨닫고 append 할 때 방문여부를 체크하도록 수정했다.