[IT/코딩테스트] 99클럽 코테 스터디10일차 TIL + BOJ2573

 

오늘의 문제

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

골드4

 

 

오늘은 문제를 보고 'bfs로 구현해야겠다' 라는 것은 생각했다.

그런데, 음.. 아직 그래프 알고리즘 골드 문제는 나에게 너무 힘겨운 것 같다....

혼자 또 우울해서 ㅋㅋㅋㅋ 두통 재발...🥲 아무리 생각해도 해결의 돌파구를 찾아내지를 못했다.

 

아래는 내가 생각했던 흐름이다.

나중에 다른 분들의 풀이를 찾아보니 생각의 흐름도 틀렸더라 🙃🙃🙃🙃

 

아, 물론 저번보다 나아진 것도 있다!

상하좌우를 살피는 부분을 제대로 작성할 수 있고 어떤 식으로 코드를 짜야하는지에 대한 감(?)

근데 이제 그 이상은 힘든...

 

 

 

그래서 우선은. 

오늘 문제는 다른 분들의 코드를 보면서 공부하는 방향을 택했다.

 

아래에 코드와 흐름대로 공부하면서 작성한 주석이 있다.

 

import sys
from collections import deque

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


# 인접 노드의 0 의 개수만큼 1년마다 줄어든다.

def bfs(x, y):
    q = deque([x, y])  # 큐 생성
    visited[x][y] = 1  # 방문 체크
    seaList = []  # 기존 노드에서 뺄 숫자 저장 리스트

    while q:
        x, y = q.popleft()
        sea = 0
        # 상하좌우 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not graph[nx][ny]:  # graph[nx][ny] 가 0인 경우
                    sea += 1  # 0인 인접 노드 개수 저장
                elif graph[nx][ny] and not visited[nx][ny]:  # 0이 아니고 방문한 적이 없는 경우
                    q.append((nx, ny))  # 방문 노드 큐에 추가
                    visited[nx][ny] = 1  # 방문 체크
        if sea > 0:
            seaList.append((x, y, sea))
    for x, y, sea in seaList:
        graph[x][y] = max(0, graph[x][y] - sea)  # 음수가 될 경우에 0 을 저장하도록

    return 1


ice = []
for i in range(n):
    for j in range(m):
        if graph[i][j]:
            ice.append((i, j))  # ice 에 빙산 위치 저장

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
year = 0

while ice:
    visited = [[0] * m for _ in range(n)]
    delList = []  # 다 녹은 위치 
    group = 0  # 빙산 개수
    for i, j in ice:
        if graph[i][j] and not visited[i][j]:
            group += bfs(i, j)  # bfs 실행
        if graph[i][j] == 0:  # bfs 실행 결과로 빙산 -> 바다 가 된 경우 체크한다.
            delList.append((i, j))  # delList 에 위치 추가
    if group > 1:  # 빙산 개수가 1이 넘으면 년 출력
        print(year)
        break  # 넘는 순간 추가 확인 불필요

    # 다 녹은 빙산은 전체 ice 에서 제거
    # 집합으로 설정해 바로 제거할 수 있도록 코드 작성
    # 위치 기준으로 저장되어 있기 때문에 다시 리스트화시키고 정렬
    ice = sorted(list(set(ice) - set(delList)))
    year += 1

# 빙산이 다 녹을 때까지 분리되지 않은 경우
if group < 2:
    print(0)

 

 

심지어 다른 분들의 코드를 보면서 나름 내 코드에 융합시키면서 작성했는데.

이상하게 런타임에러도 두번이나 발생했다.

 

주석을 너무 달아놔서 그런가.

 

 

 

사실 오늘 문제는 맞았다고 보기가 힘들고 그냥 문제 하나 공부했다는 쪽에 가깝다.

 

이번 구정 연휴에는 문제가 제공되지 않는다고 해서 오히려 다행스럽다.

26일에 토익 시험을 보고 1월 27일 ~ 2월2일 까지 하루에 한문제씩 bfs, dfs 만 풀어야겠다.

 

제발 정복해보자!! 🔥🔥🔥

할 수 있다!!

어디에내놔도부끄러운나의레벨

 

 

현재 레벨이 실버 2인데, 구정 연휴 동안 열심히 공부해서 bfs, dfs도 정복하고

실버 1 로 승급할거다!!!