softeer - 파이썬 level3 동계 테스트 시점 예측

진짜 이 문제 풀다가 화가 많이 났어요...

요즘 제가 이상한 걸수도 있는데 소프티어 문제들은 뭐랄까... 엄청 성질을 박박 긁는달까요...?^^//

제가 더 분발할게요....

소프티어 레벨3을 한번에 풀어버리는 멋진 알고리즘 왕이 되는 그날까지...⭐️

 

 🫠 풀이 접근

• 모든 얼음이 녹을 떄까지 bfs 탐색을 반복합니다.
• 이 때, visited 변수를 초기화 시키는거 잊지 말기!
• 상하좌우를 탐색할 때, 앞으로 탐색할 칸이 얼음인지 혹은 얼음이 아닌데 방문한 적이 없는 곳인지 파악해야 합니다.
  • 이렇게 하면 얼음 내부는 탐색하지 않고 얼음 밖의 영역만 탐색을 하게 됩니다!
• 두 면이 닿은 얼음 (visited >= 2)인 얼음은 녹여줍니다

 

🫠 풀이 과정

import sys
from collections import deque

def bfs():
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append([0,0])
    visited[0][0] = 1

    while queue:
        [x, y] = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < M :
                if graph[nx][ny] == 1: # 얼음이면
                    visited[nx][ny] += 1
                elif visited[nx][ny] == 0: # 얼음이 아닌데 방문한 적이 없으면
                    visited[nx][ny] = 1
                    queue.append([nx, ny])
    
    for i in range(N):
        for j in range(M):
            if visited[i][j] >= 2:  graph[i][j] = 0 # 2면이 외부랑 닿은 얼음 녹이기




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

cnt = 0
while True:
    # 얼음이 모두 녹았으면 break
    if graph.count(graph[0]) == N:
        break
    visited = [[0] * M for _ in range(N)]
    bfs()
    cnt += 1

print(cnt)

 

🫠 틀린 코드

여러분 사실 저는 아래 코드가 아직도 왜 틀린지 모르겠어요... (다시 보기 싫은 걸지도..)

지나가시다가 보시고 틀린 부분이 보인다면 알려주시면 정말 감사하겠습니다 🙇‍♀️

import sys
from collections import deque

def bfs():
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append([0,0])
    visited[0][0] = 1
    
    while queue:
        x, y = queue.popleft()
        
        # 얼음이 x,y임!
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                if maps[nx][ny] == 1: # 탐색할 다음 위치가 얼음이면
                    visited[nx][ny] += 1
                    
                elif visited[nx][ny] == 0: # 다음 위치가 얼음이 아니면
                    visited[nx][ny] = 1
                    queue.append([nx, ny])
        
        for i in range(N):
            for j in range(M):
                if visited[i][j] >= 2:
                    maps[i][j] = 0 # 두번 이상 방문한 경우 얼음 녹은걸로 바꿔주기


N, M = map(int, sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
cnt = 0

while True:
    if maps.count(maps[0]) == N:
        break

    visited = [[0] * M for _ in range(N)]
    bfs()
    cnt += 1

print(cnt)