BFS (11) 썸네일형 리스트형 [ BOJ / 파이썬 ] 4179. 불! 보호되어 있는 글입니다. [ BOJ / 파이썬 ] 2178.미로 탐색 BFS BFS문제 중 거리 측정 유형이다. BFS문제의 가장 전형적인 유형이기도 하고, 개인적으로 주구장창 풀었던 스타일이라 술술 써내려갔다. 문제 ( 링크 ) 기본적인 BFS는 방문 여부를 담을 배열을 따로 두지만, 해당 문제에서 밟아야할 공간이 1이므로 1 이상인 경우는 방문했다고 여기며 그 자리에 현재까지의 최단거리를 바로 대체해 넣는 방식으로 코드를 작성했다. 제출 1. 통과 import sys input = sys.stdin.readline from collections import deque def main(): n, m = map(int, input().split()) board = [list(map(int, list(input().strip()))) for _ in range(n)] dx .. [ BOJ / 파이썬 ] 2667 단지 번호 붙이기 - 30분 소요 - 와 .. ㅠㅜ 실수해서 10분을 날려먹었다.. bfs처음 시작하면서 q에 첫 원소 넣을 때 해당 원소를 방문처리하는 걸 놓쳤다. - 덕분에 이중 방문해서 예상 값보다 1씩 더 나오는 에러 잡느라 시간 걸렸다. - 문제 자체는 단순한 bfs적용, 2583 영역 구하기랑 같은 맥락의 문제였다. - python list unpaking operator쓰는 법 까먹어서 검색해서 찾아옴.. import sys input = sys.stdin.readline from collections import deque n = int(input()) board = [list(map(int, list(input().strip()))) for _ in range(n)] visited = [[False]*n .. [ BOJ / 파이썬 ] 2583 영역 구하기 누가봐도 bfs문제! ㅡ [1] 상자를 칠한다. (2중 for문으로 칠해주기) : 1에서 전에 배운 누적합을 사용해볼까 헀는데 옹? input 최대값이 100밖에 안되길래 그냥 2중for문으로 칠했다. 대신 이미 칠해진 부분은 패스하도록 설정 [2] 안 칠해진 영역의 개수와 넓이를 구한다.(bfs 이용) 이 부분은 전형적인 bfs문제! ㅡ : 사실 상자가 뒤집혀 있는데 영역 개수와 넓이 구하는 거라 뒤집힌 채로 그냥 구해도 괜찮을 것 같아 고대로 받아서 계산했다. : 근데 이렇게 하니까 좌표값이 개인적으로 자꾸 헷갈렸다. 그래서 디버깅하느라 시간이 조금 소요되어서 아쉽다. : 공간감각이 떨어져서 좌표에서 꼬이면 멘탈 나가는 것 같은데.. 흠.. 조심하자! import sys input = sys.stdi.. [ BOJ / 파이썬 ] 2206 벽 부수고 이동하기 / 제출 1 / ( 소요 시간 : 30분 ) import sys input = sys.stdin.readline from collections import deque dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] n, m = map(int, input().split()) board = [] walls = [] for i in range(n): line = list(map(int, input().strip())) for j in range(m): if line[j] == 1: walls.append((i, j)) board.append(line) result = [] for wall in walls: i, j = wall board[i][j] = 0 q = deque([(0, 0)]).. [ BOJ / 파이썬 ] 1012 유기농 배추 / 첫 번째 제출 / import sys from collections import deque input = sys.stdin.readline T = int(input()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] for t in range(T): # 초기화 ## 가로, 세로, 배추 개수 m, n, k = map(int, input().split()) farm = [[0] * m for _ in range(n)] visited = [[False] * m for _ in range(n)] q = deque([]) cabbageq = deque([]) for i in range(k): y, x = map(int, input().split()) farm[x][y] = 1 worm =.. [ BOJ / 파이썬 ] 1697 숨바꼭질 / 제출 1 / from collections import deque n, k = map(int, input().split()) array = [0] * 1000001 q = deque([n]) def bfs(): while q: x = q.popleft() if x == k or array[k] != 0 : return array[k] if 0 [ BOJ / 파이썬 ] 4179 불! / 제출 1 / from collections import deque import copy r, c = map(int, input().split()) board = [list(input()) for _ in range(r)] # 상 우 하 좌 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] jihoonBoard = copy.deepcopy(board) fireBoard = copy.deepcopy(board) jihoonStart = [] fireStart = [] for x in range(r): for y in range(c): if board[x][y] == 'J': jihoonBoard[x][y] = 1 fireBoard[x][y] = 0 jihoonStart = [(x, y).. [ BOJ / 파이썬 ] 7576 토마토 / 풀이 1 / from collections import deque m, n = map(int, input().split()) tomatoes = [list(map(int, input().split())) for _ in range(n)] dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] ripped = [[False] * m for _ in range(n)] q = deque([]) day = 0 def bfs(q): new_q = deque([]) while q: x, y = q.pop() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 [ BOJ / 파이썬 ] 2178 미로 탐색 / 제출 1 / 첫 제출에 틀렸습니다. 가 나와서 당황했었다. 잘 .. 한 것 같은데 뭐지.. 복사하면서 줄 바꿈 등이 잘 못 옮겨졌었던 것이었습니다. 동일 소스코드를 줄정렬한 것이 아래 코드입니다. / 제출 2 / ### from collections import deque n, m = map(int, input().split()) board = [list(map(int, input())) for _ in range(n)] visited = [[False] * m for _ in range(n)] visited[0][0] = True q = deque([[0, 0]]) # 하 우 상 좌 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] # n-1, m-1 도착할 때까지 최단거리 whi.. 이전 1 2 다음 목록 더보기
