글 읽기 - bfs 질문입니다

kim98 1년 전 0

bfs를 구현을 했는데요 무엇이 문제인지 모르겠습니다.

bfs구현시에 bfs(y,x)로 푸는 것이 더 좋다 이런말이 있던데 왜 그런지 알 수 있을까요??

알려주세요ㅠㅠ

그리고 추가로 좌표상의 x,y랑 2차원 배열에서 x,y가 혼동이 되서 코딩을 할 때도 문제가 되는것 같습니다.

이럴때는 어떻게 잡고 하는게 좋을까요?

from collections import deque

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(n)]
visit = [[False] * m for _ in range(n)]

cnt = 0
maxv = 0

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

def bfs(x,y):
  rs = 1
  q = deque()
  q.append((x,y))

  while q:
    ex, ey = q.popleft()
    for k in range(4):
      nx = ex + dx[k]
      ny = ey + dy[k]
      if 0<=ny<n and 0<=nx<m:
        if map[nx][ny] == 1 and visit[nx][ny] == False:
          rs += 1
          visit[nx][ny] = True
          q.append((nx,ny))
  return rs

for i in range(n):
  for j in range(m):
    if map[i][j] == 1 and visit[i][j] == False:
      visit[i][j] = True
      cnt += 1
      maxv = max(maxv, bfs(i,j))

print(cnt)
print(maxv)

qhwhehwh 1년 전 1

26번 라인에 ny랑 nx 위치가 바뀐듯 합니다.

kim98 1년 전 1

감사합니다~ 혹시 bfs구현시에 y,x로 바꾸어서 하는 이유가 따로있을까요~?

qhwhehwh 1년 전 1

제 개인적인 생각에 바꾸어야 할 이유는 없습니다. 그냥 본인이 행, 열로 잡고 싶은 변수의 이름만 달라진다고 생각합니다.
행렬에서 열을 x라는 변수를 쓰냐, y라는 변수로 쓰냐의 차이입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

bfs 질문입니다

kim98 1년 전 0

qhwhehwh 1년 전 1

kim98 1년 전 1

qhwhehwh 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말