GitHub ID : soohyun-dev
윤수현의 개발 공간
GitHub ID : soohyun-dev
전체 방문자
오늘
어제
  • 분류 전체보기 (918)
    • 성장기록 (49)
      • 성장기록 (3)
      • 우아한테크코스 (16)
      • 프로젝트 (15)
      • TIL (14)
      • 테오의 스프린트 (1)
    • 프로그래밍언어 (88)
      • C언어 (14)
      • HTML\CSS (12)
      • JavaScript (7)
      • React (23)
      • Python (11)
      • JAVA (14)
      • TypeScript (6)
    • 알고리즘 공부 (736)
      • 코드업 - 파이썬 (108)
      • 백준 - 파이썬 (468)
      • 백준 - 자바스크립트 (125)
      • 프로그래머스 - 파이썬 (1)
      • 프로그래머스 - 자바스크립트 (34)
    • 책 리뷰 (9)
      • 프로그래밍 (3)
      • 독서 (6)
    • 전자기기 (1)
    • 일상, 일기 (18)
    • 기술 세미나 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 코드업
  • 코드업파이썬
  • 백준파이썬
  • 영어독해
  • 백준풀이
  • 프로그래밍언어
  • 프로그래머스
  • 자바스크립트
  • 독해
  • PYTHON
  • javascript
  • 프론트엔드
  • 프로그래머스자바스크립트
  • 백준
  • 코딩
  • 파이썬
  • 영어
  • 프로그래머스풀이
  • 코테
  • 코딩테스트

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
GitHub ID : soohyun-dev

윤수현의 개발 공간

백준/ Gold 2 문제 , 백준 파이썬 16946 , 벽 부수고 이동하기 4 [BFS]
알고리즘 공부/백준 - 파이썬

백준/ Gold 2 문제 , 백준 파이썬 16946 , 벽 부수고 이동하기 4 [BFS]

2022. 8. 12. 12:23

백준/ Gold 2 문제 , 백준 파이썬 16946 , 벽 부수고 이동하기 4 [BFS]

 

 

시간 초과 해결이 제일 빡세다

 

풀이 시간

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
접근 방법은 잘했는데 시간초과를 해결하는데 오래 걸렸다.
나는 MAP리스트에 인접 0의 갯수를 저장해서 나중에 그 값들을 더하는 식으로 짰는데,
이렇게 하면 시간 초과가 어디선가 발생한다.
약간의 로직만 바꿔서 인접0의 갯수는 dict를 사용해 저장하고 MAP에는 그룹의 번호만 남기는 식으로 풀어야한다.

 

 

 

 

문제 출처

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

 

16946번: 벽 부수고 이동하기 4

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이

www.acmicpc.net

 

초기 풀이

MAP리스트에 인접 0의 갯수들을 저장

시간초과 발생

 

 

풀이

 

 

1. 기본 세팅

 

1. 상하좌우

 

2. N 행의 MAP 리스트 선언

 

3. 그룹을 지정할 N 행의 리스트 선언

 

 

2. BFS

 

우선 재방문을 방지 하기 위해 visited 를 사용한다.

 

이때 bfs에는 x,y (행과 열의 위치) 와 C라는 그룹번호를 전달 받게 되는데

 

인접 0에다가 부여받은 그룹번호들을 S리스트에다가 할당해준다.

 

이후 총 몇개에다가 할당했는지 cnt 변수에 저장해두고

 

이 cnt를 return 시킨다.

 

 

3. BFS 호출 및 처리

각 그룹이 몇개의 인접 0들로 이루어져있는지를 dict 에다가 저장해둔다.

 

return 받은 cnt 값을 result 에 저장해두고 그룹 번호 c : result 값으로 dict 에 저장

 

 

 

4. 최종 리스트 생성

 

이제 S리스트에서 0인 값들은 MAP리스트에서 벽이 있던 자리와 같다.

 

이 부분들의 위치에서 각 인접 그룹번호에 맞는 값들을 더해주면된다.

 

이때 중복되게 더함을 방지 하기 위하여 set 을 사용한다.

 

 

4 5
11001
00111
01010
10101

 

예를 들면 (0행부터 시작) 2행 1열의 1은 왼쪽과 위쪽이 같은 그룹이다.

 

그래서 이 둘 중 하나의 값만 더해줘야하므로 set을 이용해 중복을 방지한다.

 

tmp 리스트에다가 더해줄 그룹 번호들을 넣어주고 이후 각 그룹번호들이 가지고 있는 각 인접 0들의 갯수들을 D에다가 더해 출력한다.

 

이때 인접 위치뿐만이 아닌 자기 자신 위치도 세줘야하기때문에 D+=1 을 더 해준 뒤 10으로 나눈 나머지를 출력한다.

 

 

정답

 

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

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

N,M=map(int,input().split())
MAP=[list(map(int,input().rstrip())) for _ in range(N)]
S=[[0 for _ in range(M)] for _ in range(N)]

def bfs(x,y,C):
    dq=deque()
    dq.append([x,y])
    visited[x][y]=1
    cnt=1
    S[x][y]=C
    while dq:
        X,Y=dq.popleft()
        for a,b in dr:
            mx,my=X+a,Y+b
            if 0<=mx<N and 0<=my<M:
                if MAP[mx][my]==0:
                    if visited[mx][my]==0:
                        MAP[mx][my]=1
                        dq.append([mx,my])
                        visited[mx][my]=1
                        cnt+=1
                        S[mx][my]=C
    return cnt
c=1
MAX=0
dict={}
visited=[[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
    for j in range(M):
        if MAP[i][j]==0:
            result=bfs(i,j,c)
            dict[c]=result
            c+=1

for i in range(N):
    for j in range(M):
        D=0
        tmp=set()
        if S[i][j]==0:
            for a,b in dr:
                mi,mj=i+a,j+b
                if 0<=mi<N and 0<=mj<M:
                    if S[mi][mj]!=0:
                        tmp.add(S[mi][mj])
            for m in tmp:
                D+=dict[m]
            D+=1
        print(D%10,end='')
    print()

 

 

 

 

 

 

 

반응형

'알고리즘 공부 > 백준 - 파이썬' 카테고리의 다른 글

백준/ Gold 4 문제 , 백준 파이썬 11559 , Puyo Puyo [BFS]  (0) 2022.08.12
백준/ Gold 4 문제 , 백준 파이썬 5427 , 불 [BFS]  (0) 2022.08.12
백준/ Bronze 3 문제 , 백준 파이썬 16479 , 컵라면 측정하기  (0) 2022.08.12
백준/ Silver 5 문제 , 백준 파이썬 2018 , 수들의 합 5  (0) 2022.08.12
백준/ Gold 5 문제 , 백준 파이썬 17836, 공주님을 구해라! [BFS]  (0) 2022.08.11
    '알고리즘 공부/백준 - 파이썬' 카테고리의 다른 글
    • 백준/ Gold 4 문제 , 백준 파이썬 11559 , Puyo Puyo [BFS]
    • 백준/ Gold 4 문제 , 백준 파이썬 5427 , 불 [BFS]
    • 백준/ Bronze 3 문제 , 백준 파이썬 16479 , 컵라면 측정하기
    • 백준/ Silver 5 문제 , 백준 파이썬 2018 , 수들의 합 5
    GitHub ID : soohyun-dev
    GitHub ID : soohyun-dev
    환영합니다!😊 이곳은 저의 개발에 관한 내용들을 정리하는 공간입니다. 알고리즘 풀이에도 관심이 많아요. 좋은 하루 되세요~! github : soohyun_dev

    티스토리툴바